Inne rodzaje analizy czasu pracy oprócz najgorszego przypadku, średniego przypadku itp.?

Oto kilka sposobów analizy czasu działania algorytmu:

1) Analiza najgorszego przypadku: czas działania w najgorszym przypadku.

2) Analiza średnich przypadków: oczekiwany czas działania w przypadkowej instancji.

3) Amortyzowana analiza: średni czas działania w najgorszej sekwencji przypadków.

4) Wygładzona analiza: oczekiwany czas działania w najgorszym przypadkowo zaburzonym wystąpieniu.

5) Analiza przypadków ogólnych: czas działania w najgorszym ze wszystkich oprócz niewielkiego podzbioru instancji.

Moje pytanie: czy to pełna lista?

Optymalność wystąpienia jest bardzo interesującą właściwością algorytmów. Można uogólnić pojęcia optymalności instancji i opracować zaskakująco ciekawe pojęcia, które obejmują analizę najgorszego i przeciętnego przypadku.

Chociaż nie podlega on wyłącznie tradycyjnej analizie algorytmów, sam w sobie jest interesujący. Pomysł w artykule Afshani-Barbay-Chana (FOCS '09), który omawia algorytm geometryczny, uważa, że ​​wydajność algorytmu nie zależy od kolejności wprowadzania danych (co jest istotne dla ich konkretnego problemu).

Można to uogólnić w następujący sposób: Dla każdej partycji algorytmu dane wejściowe do klas równoważności i uważają wydajność algorytmu za jakąś kolektywną statystykę w stosunku do średniej wydajności dla każdej z tych klas równoważności.

Analiza najgorszego przypadku po prostu patrzy na dane wejściowe jako indywidualne klasy równoważności i oblicza maksymalny czas działania. Analiza średnich przypadków analizuje trywialną klasę równoważności, która jest pojedynczą obejmującą wszystkie dane wejściowe. W pracy Afshani-Barbay-Chan ich algorytm jest optymalny, jeśli dane wejściowe są podzielone na klasy permutacji (tj. Wydajność nieświadomości porządku).

Nie jest jasne, czy prowadzi to do jakichkolwiek nowych paradygmatów analizy algorytmów. Kurs Tima Roughgarden ma kilka doskonałych motywujących przykładów i obejmuje różne metody analizy algorytmów.

Mam jeszcze dwie listy, które są nieco podobne.

1. Analiza sparametryzowana wyraża czas działania jako funkcję dwóch wartości zamiast jednej, wykorzystując dodatkowe informacje o danych wejściowych mierzonych w tak zwanym `` parametrze ''. Jako przykład weźmy problem z zestawem niezależnym. Najlepszy czas działania dla ogólnego przypadku ma postać dla pewnej stałej . Jeśli teraz weźmiemy jako parametr szerokość wykresu i reprezentujemy go parametrem , zestaw niezależny można obliczyć w czasie . Dlatego jeśli szerokość jest niewielka w porównaniu z całkowitym rozmiarem wykresu , wówczas ten sparametryzowany algorytm jest znacznie szybszy.1 < c < 2 k O ( 2 k n O ( 1 ) ) k $O(c^n n^{O(1)})$$1 < c < 2$$k$$O(2^k n^{O(1)})$$k$$n$

2. Analiza wrażliwa na wyniki jest techniką stosowaną do problemów konstrukcyjnych, a także uwzględnia wielkość danych wyjściowych w wyrażeniu w czasie wykonywania. Dobrym przykładem jest problem określania punktów przecięcia zestawu segmentów linii w płaszczyźnie. Jeśli się nie mylę, można obliczyć przecięcia w czasie gdzie jest liczbą skrzyżowań.$O(n \log n + k)$$k$

Analiza adaptacyjna mierzy czas działania algorytmów wielomianu czasowego w odniesieniu do wielu parametrów. Na przykład chcesz algorytm sortowania, który działa w czasie, ale jest znacznie szybszy, gdy dane wejściowe są prawie posortowane. Analiza adaptacyjna algorytmu sortowania uwzględniłaby liczbę odwrotnych par, liczbę przebiegów, gdzie przebieg jest maksymalną posortowaną kolejną częścią danych wejściowych lub entropią danych wejściowych.$O(n \log n)$

Wygląda jak analiza sparametryzowana dla algorytmów wielomianowych i wydaje się, że analiza wrażliwa na wynik mieści się w tej kategorii.

Istnieje również analiza „ wysokiego prawdopodobieństwa ” (dla algorytmów losowych), w której w każdym przypadku martwisz się, jak dobrze Twój algorytm będzie działał przez większość czasu, ale może całkowicie zrezygnować z niewielkiej części czasu. Jest to powszechne w teorii uczenia się.

Możesz dodać losowość do swojego algorytmu i połączyć go ze wszystkimi powyższymi. Otrzymasz np. Oczekiwany czas działania w najgorszym przypadku (najgorszy przypadek, ale uśredniony dla wszystkich możliwych sekwencji losowych rzutów monetą w algorytmie) i czas najgorszego przypadku z dużym prawdopodobieństwem (ponownie, najgorszy przypadek, ale prawdopodobieństwo przewrócenia losowej monety w algorytmie).

Analiza bijectywna jest sposobem na porównanie dwóch algorytmów (Spyros Angelopoulos, Pascal Schweitzer: Aktualizacja stronicowania i listy w ramach analizy bijective. J. ACM 60, 2013): Z grubsza algorytm A jest lepszy niż algorytm B na wejściach o długości n, jeśli istnieje bijection f na wejściach o długości n taki, że A wykonuje na wejściu x co najmniej tak dobre, jak B na f (x).

Analiza konkurencji

Służy do porównywania algorytmów online z algorytmami wydajności offline. Zobacz stronę wikipedii . Problem aktualizacji listy jest klasycznym przykładem.

Analiza konkurencji W algorytmie zastępowania stron jedna metoda przeważa drugą, zmniejszając brakującą stronę. Mniej brakujących stron ilustruje „mniej czasu działania”. Poza tym analiza konkurencyjna jest metodą względnego porównania dwóch metod. Dobrą książką referencyjną jest „OBLICZANIE ONLINE I ANALIZA KONKURENCYJNA” Allana Borodina.