Czy istnieje magia analizy algorytmów?

Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się być dostosowana do indywidualnych potrzeb.

Z drugiej strony odpowiedzi na inne ogólne pytanie wyjaśniają szerszy obraz (w szczególności w odniesieniu do analizy asymptotycznej) kilkoma przykładami, ale nie pokazują, jak zabrudzić sobie ręce.

Czy istnieje ustrukturyzowana, ogólna metoda analizy kosztów algorytmów? Kosztem może być czas działania (złożoność czasu) lub inna miara kosztów, taka jak liczba wykonanych porównań, złożoność przestrzeni lub coś innego.

^{To ma stać się pytaniem referencyjnym, które można wykorzystać do wskazania początkującym; stąd jego szerszy niż zwykle zakres. Prosimy o podanie ogólnych, dydaktycznie przedstawionych odpowiedzi, które są zilustrowane co najmniej jednym przykładem, ale mimo to obejmują wiele sytuacji. Dzięki!}

Tłumaczenie kodu na matematykę

Biorąc pod uwagę (mniej lub bardziej) formalną semantykę operacyjną , możesz dosłownie przetłumaczyć (pseudo-) kod algorytmu na wyrażenie matematyczne, które daje wynik, pod warunkiem, że możesz manipulować tym wyrażeniem w użytecznej formie. Działa to dobrze w przypadku dodatkowych miar kosztów, takich jak liczba porównań, zamiany, zestawienia, dostęp do pamięci, cykle niektórych abstrakcyjnych potrzeb maszyny i tak dalej.

Przykład: Porównania w Bubblesort

Rozważ ten algorytm, który sortuje daną tablicę A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Powiedzmy, że chcemy przeprowadzić zwykłą analizę algorytmu sortowania, czyli policzyć liczbę porównań elementów (wiersz 5). Od razu zauważamy, że ta ilość nie zależy od zawartości tablicy A, tylko od jej długości . Możemy więc przetłumaczyć (zagnieżdżone) pętle dosłownie na (zagnieżdżone) sumy; zmienna pętli staje się zmienną sumującą, a zakres jest przenoszony. Otrzymujemy:$n$for

,$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$

gdzie to koszt każdej realizacji linii 5 (którą liczymy).$1$

Przykład: zamiana w Bubblesort

Przez oznaczę podprogram składający się z wierszy do i przez C i , j koszty wykonania tego podprogramu (jeden raz).$P_{i,j}$ij$C_{i,j}$

Powiedzmy, że chcemy policzyć swapy , czyli jak często jest wykonywane. Jest to „blok podstawowy”, czyli podprogram, który jest zawsze wykonywany atomowo i ma pewien stały koszt (tutaj 1 ). Kontrakty na takie bloki to jedno z przydatnych uproszczeń, które często stosujemy bez zastanowienia się nad tym.$P_{6,8}$$1$

Z podobnym tłumaczeniem jak powyżej dochodzimy do następującej formuły:

.$\qquad\displaystyle C_{\text{swaps}}(A) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

oznacza stan tablicy przed ( i , j ) -tą iteracją P 5 , 9 .$A^{(i,j)}$$(i,j)$$P_{5,9}$

Zauważ, że używam zamiast n jako parametru; wkrótce zobaczymy dlaczego. Nie dodam i i j jako parametrów C 5 , 9, ponieważ koszty nie zależą od nich tutaj ( to znaczy w modelu kosztu jednolitego ); w ogóle mogą.$A$$n$$i$$j$$C_{5,9}$

Oczywiście koszty zależą od zawartości A (wartości, a konkretnie), więc musimy to uwzględnić. Teraz stajemy przed wyzwaniem: w jaki sposób „rozpakowujemy” C 5 , 9 ? Cóż, możemy uczynić zależność od treści A wyraźnym:$P_{5,9}$$A$A[j]A[j+1]$C_{5,9}$$A$

.$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$

W przypadku dowolnej tablicy wejściowej koszty te są dobrze określone, ale chcemy bardziej ogólnego zestawienia; musimy przyjąć silniejsze założenia. Przeanalizujmy trzy typowe przypadki.

1. Najgorszy przypadek

   Wystarczy spojrzeć na sumę i zauważyć, że , możemy znaleźć trywialną górną granicę kosztów:$C_{5,9}(A^{(i,j)}) \in \{0,1\}$

   .$\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$

   Ale czy może się to zdarzyć , tj. Czy osiągnięto dla tej górnej granicy? Jak się okazuje, tak: jeśli wprowadzimy odwrotnie posortowaną tablicę odrębnych parami elementów, każda iteracja musi wykonać swap¹. Dlatego wyprowadziliśmy dokładną liczbę najgorszych przypadków zamiany Bubblesort.$A$

2. Najlepszy przypadek

   I odwrotnie, istnieje trywialna dolna granica:

   .$\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$

   Może się to również zdarzyć: w tablicy, która jest już posortowana, Bubblesort nie wykonuje pojedynczej zamiany.

3. Przeciętny przypadek

   Najgorszy i najlepszy przypadek otwiera spore luki. Ale jaka jest typowa liczba zamian? Aby odpowiedzieć na to pytanie, musimy zdefiniować, co oznacza „typowy”. Teoretycznie nie mamy powodu, aby preferować jeden wkład nad drugim, dlatego zwykle zakładamy jednolity rozkład wszystkich możliwych danych wejściowych, to znaczy każde wejście jest jednakowo prawdopodobne. Ograniczamy się do tablic z odrębnymi parami elementów, a zatem zakładamy model losowej permutacji .

   Następnie możemy przepisać nasze koszty w ten sposób²:

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

   Teraz musimy wyjść poza zwykłą manipulację sumami. Patrząc na algorytm, zauważamy, że każda zamiana usuwa dokładnie jedną inwersję w (wymieniamy tylko sąsiadów3). Oznacza to, że liczba wykonywanych na swapy A jest dokładnie liczba inwersji inw ( A ) z . W ten sposób możemy zastąpić dwie wewnętrzne sumy i uzyskać$A$$A$$\operatorname{inv}(A)$$A$

   .$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$

   Na szczęście dla nas ustalono średnią liczbę inwersji

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

   co jest naszym końcowym wynikiem. Należy pamiętać, że jest to dokładnie połowa najgorszych kosztów.

1. Zauważ, że algorytm został starannie sformułowany, aby i = n-1nie została wykonana „ostatnia” iteracja z zewnętrzną pętlą, która nigdy nic nie robi.
2. „ ” jest notacją matematyczną dla „wartości oczekiwanej”, która tutaj jest tylko średnią.$\mathbb{E}$
3. Uczymy się po drodze, że żaden algorytm, który zamienia tylko sąsiednie elementy, nie może być asymptotycznie szybszy niż Bubblesort (nawet średnio) - liczba inwersji jest dolną granicą dla wszystkich takich algorytmów. Dotyczy to np. Sortowania wstawiania i sortowania wyboru .

Ogólna metoda

W przykładzie widzieliśmy, że musimy przełożyć strukturę kontroli na matematykę; Przedstawię typowy zestaw reguł tłumaczenia. Zauważyliśmy również, że koszt dowolnego podprogramu może zależeć od aktualnego stanu , czyli (z grubsza) bieżących wartości zmiennych. Ponieważ algorytm (zwykle) modyfikuje stan, ogólna metoda jest nieco trudna do odnotowania. Jeśli poczujesz się zdezorientowany, sugeruję, abyś wrócił do przykładu lub sam wymyślił.

Oznaczamy bieżącym stanem (wyobraź sobie, że jest to zestaw przypisań zmiennych). Kiedy wykonujemy program zaczynający się w stanie ψ , kończymy w stanie ψ / P (pod warunkiem, że zakończy się).$\psi$P$\psi$$\psi / \mathtt{P}$P

• Indywidualne oświadczenia

  Biorąc pod uwagę tylko jedną instrukcję S;, przypisujesz jej koszt . Zazwyczaj będzie to stała funkcja.$C_S(\psi)$

• Wyrażenia

  Jeśli masz wyrażenie Eformularza E1 ∘ E2(powiedzmy, wyrażenie arytmetyczne, gdzie ∘może być dodawanie lub mnożenie, sumujesz koszty rekurencyjnie:

  .$\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$

  Zauważ, że

  • koszt operacji może nie być stały, ale zależy od wartości E 1 i E 2 oraz$c_{\circ}$$E_1$$E_2$
  • ocena wyrażeń może zmienić stan w wielu językach,

  więc być może będziesz musiał być elastyczny z tą regułą.

• Sekwencja

  Biorąc pod uwagę program Pjako sekwencję programów Q;R, dodajesz koszty do

  .$\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$

• Warunkowe

  Biorąc pod uwagę program Pformularza if A then Q else R end, koszty zależą od stanu:

  $\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

  Ogólnie rzecz biorąc, ocena Amoże bardzo dobrze zmienić stan, stąd aktualizacja kosztów poszczególnych oddziałów.

• For-Loops

  Biorąc pod uwagę program Pformularza for x = [x1, ..., xk] do Q end, przypisz koszty

  $\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

  gdzie jest stanem przed przetwarzaniem wartości , tj. po iteracji z ustawieniem na ..., .$\psi_i$Qxixx1xi-1

  Zwróć uwagę na dodatkowe stałe dla utrzymania pętli; należy utworzyć zmienną pętli ( ) i przypisać jej wartości ( c step_for ). Jest to istotne, ponieważ$c_{\text{init_for}}$$c_{\text{step_for}}$

  • obliczanie następnego ximoże być kosztowne i
  • for-loop z pustym korpusie (np po uproszczeniu w zachodzącym z określonym kosztem w najlepszym przypadku) nie ma zerowe koszty, jeżeli spełnia ona iteracji.

• Podczas pętli

  Biorąc pod uwagę program Pformularza while A do Q end, przypisz koszty

  $\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

  Po sprawdzeniu algorytmu ta powtarzalność często może być ładnie przedstawiona jako suma podobna do sumy dla pętli for.

  Przykład: Rozważ ten krótki algorytm:

  while x > 0 do    1
    i += 1          2
    x = x/2         3
  end               4
  

  Stosując regułę, otrzymujemy

  $\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else} \end{cases}$

  $c_{\dots}$ix

  $C_{1,4}$i

  $\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

  To rozwiązuje z podstawowych środków do

  $\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$

  $\psi = \{ \dots, x := 5, \dots\}$$\psi(x) = 5$

• Wywołania procedur

  Biorąc pod uwagę program Pformularza M(x)dla niektórych parametrów, xgdzie Mjest procedura z (nazwanym) parametrem p, przypisz koszty

  $\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$

  $c_{\text{call}}$$\psi$

  Zastanawiam się nad niektórymi problemami semantycznymi, które możesz mieć z tym państwem tutaj. Będziesz chciał rozróżnić stan globalny i takie lokalne wywołania procedur. Załóżmy, że przekazujemy tutaj tylko stan globalny i Motrzymujemy nowy stan lokalny, inicjowany przez ustawienie wartości pna x. Ponadto xmoże być wyrażeniem, które (zwykle) zakładamy, że zostanie ocenione przed przekazaniem.

  Przykład: Rozważ procedurę

  fac(n) do                  
    if ( n <= 1 ) do         1
      return 1               2
    else                     3
      return n * fac(n-1)    4
    end                      5
  end                        
  

  Zgodnie z regułami otrzymujemy:

  $\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\}) &= C_{1,5}(\{n := n_0\}) \\ &= c_{\leq} + \begin{cases} C_2(\{n := n_0 \}) &, n_0 \leq 1 \\ C_4(\{n := n_0 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}$

  Pamiętaj, że pomijamy stan globalny, ponieważ facwyraźnie nie ma dostępu do żadnego. Ten konkretny nawrót jest łatwy do rozwiązania

  $\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

Omówiliśmy funkcje językowe, które napotkasz w typowym pseudo-kodzie. Uważaj na ukryte koszty podczas analizy pseudo kodu wysokiego poziomu; w razie wątpliwości rozwiń się. Notacja może wydawać się nieporęczna iz pewnością jest kwestią gustu; wymienionych pojęć nie można jednak zignorować. Jednak z pewnym doświadczeniem będziesz mógł od razu zobaczyć, które części stanu są istotne dla której miary kosztów, na przykład „rozmiar problemu” lub „liczba wierzchołków”. Resztę można upuścić - to znacznie upraszcza sprawę!

Jeśli uważasz, że teraz jest to zbyt skomplikowane, informujemy: to jest ! Wyprowadzenie dokładnych kosztów algorytmów w dowolnym modelu, który jest tak blisko rzeczywistych maszyn, że umożliwia przewidywanie czasu wykonywania (nawet względnego), jest trudnym przedsięwzięciem. I to nawet nie bierze pod uwagę buforowania i innych nieprzyjemnych efektów na prawdziwych maszynach.

Dlatego analiza algorytmów jest często upraszczana do tego stopnia, że ​​jest matematycznie wykonalna. Na przykład, jeśli nie potrzebujesz dokładnych kosztów, możesz przeszacować lub niedocenić w dowolnym momencie (dla górnej lub dolnej granicy): zmniejszyć zestaw stałych, pozbyć się warunków warunkowych, uprościć sumy i tak dalej.

Uwaga na temat kosztów asymptotycznych

$n$

Jest to (często) uczciwe, ponieważ abstrakcyjne stwierdzenia mają pewne (generalnie nieznane) koszty w rzeczywistości, w zależności od maszyny, systemu operacyjnego i innych czynników, a krótkie czasy działania mogą być zdominowane przez system operacyjny ustawiający proces przede wszystkim. W każdym razie masz jakieś zaburzenia.

Oto jak analiza asymptotyczna odnosi się do tego podejścia.

1. Zidentyfikuj dominujące operacje (które powodują koszty), to znaczy operacje, które występują najczęściej (aż do stałych czynników). W przykładzie Bubblesort możliwym wyborem jest porównanie w linii 5.

   Alternatywnie, powiąż wszystkie stałe operacji elementarnych ich maksymalną (z góry) wzgl. ich minimum (od dołu) i wykonaj zwykłą analizę.

2. Przeprowadź analizę, korzystając z liczenia wykonania tej operacji jako kosztu.
3. $O$$\Omega$

$O$

Dalsza lektura

Istnieje wiele innych wyzwań i sztuczek w analizie algorytmów. Oto kilka zalecanych lektur.

• Jak wymyślić środowisko uruchomieniowe algorytmów?
  Jak opisywać algorytmy, je udowadniać i analizować?
• Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?
  Jak możemy założyć, że podstawowe operacje na liczbach wymagają stałego czasu?
  Co stanowi jedną jednostkę czasu w analizie środowiska wykonawczego?
• Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb
• Podstawy amortyzacji

Istnieje wiele pytań oznaczonych analizą algorytmów, które wykorzystują techniki podobne do tego.

Liczba wykonanych wyciągów

Istnieje inna metoda, której mistrz Donald E. Knuth w swojej serii The Art of Computer Programming . W przeciwieństwie do tłumaczenia całego algorytmu na jedną formułę , działa on niezależnie od semantyki kodu po stronie „zestawiania rzeczy” i pozwala zejść na niższy poziom tylko wtedy, gdy jest to konieczne, zaczynając od widoku „orła oka”. Każde stwierdzenie może być analizowane niezależnie od reszty, co prowadzi do bardziej przejrzystych obliczeń. Jednak technika ta dobrze nadaje się do dość szczegółowego kodu, nie tyle pseudo kodu wyższego poziomu.

Metoda

Zasadniczo jest to dość proste:

1. Przypisz każdemu zestawieniu nazwę / numer.
2. $S_i$$C_i$
3. $S_i$$e_i$

4. Oblicz całkowite koszty

   $\qquad\displaystyle C = \sum_{i} e_i \cdot C_i$

Możesz wstawić oszacowania i / lub wielkości symboliczne w dowolnym punkcie, osłabiając odpowiednio. odpowiednio uogólniając wynik.

$e_{77} \in O(n \log n)$

Przykład: wyszukiwanie w pierwszej kolejności

Rozważ następujący algorytm przechodzenia przez wykres:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

$\{0,\dots,n-1\}$$m$

$A$$B$$C$$e_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

$e_8 = e_3-1$foodfs$e_6 = e_5 + e_7$while

$A=1$foo$B = n$$C = 2m$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

To prowadzi nas do całkowitych kosztów dokładnie

$\qquad\begin{align*} C(n,m) = (C_1 + C_2 - C_8) &+\ n \cdot (C_3 + C_4 + C_5 + C_6 + C_8) \\ &+\ 2m \cdot (C_6 + C_7 + C_9) \;. \end{align*}$

$C_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

i dostać

$\qquad\displaystyle C_{\text{mem}}(n,m) = 3n + 4m$

Dalsza lektura

Zobacz na dole mojej drugiej odpowiedzi .

Analiza algorytmów, podobnie jak dowodzenie twierdzeń, jest w dużej mierze sztuką (np. Istnieją proste programy (takie jak problem Collatza) ), których nie umiemy analizować). Możemy przekonwertować problem złożoności algorytmu na matematyczny, as kompleksowo odpowiedział Raphael , ale następnie, aby wyrazić zależność od kosztu algorytmu w zakresie znanych funkcji, musimy:

1. Użyj technik, które znamy z istniejących analiz, takich jak znajdowanie granic na podstawie zrozumienie nawrotów lub sumę / całki, które możemy obliczyć.
2. Zmień algorytm na coś, co wiemy, jak analizować.
3. Wymyśl zupełnie nowe podejście.