Złożoność algorytmu

Złożoność algorytmu

> LeekScript samouczek

Główny pomysł

Aby oszacować liczbę operacji, które zużyje funkcja lub algorytm, warto mieć pojęcie o związku między rozmiarem przekazywanych mu argumentów lub rozmiarem parametru a maksymalną liczbą wykonywanych operacji . Nazywa się to złożonością algorytmiczną.

Zacznijmy od prostego przykładu: pętli for.

for (var i=0; i N mamy f(n) < K x g(n).*

Dobra, proszę bardzo, wyrzuciłem z siebie wielkie słowa. Co właściwie oznacza ta definicja? Że funkcja f rośnie „nie szybciej” niż g wraz ze wzrostem n. f może być większe niż g, ale stosunek tych dwóch jest zawsze mniejszy niż pewna liczba (K definicji). Zastosujmy to do kodu: weźmy jako (matematyczną) funkcję f maksymalną liczbę operacji wykonywanych przez dany fragment kodu, biorąc pod uwagę rozmiar jego danych wejściowych. Szukamy prostej funkcji g takiej, że f(n)=O(g(n)). Z grubsza sprowadza się to do zmierzenia największej liczby powtórzeń podstawowych instrukcji w kodzie (koszt tych instrukcji jest w ten sposób zamiatany pod dywan: jest to K definicji).

Przykłady

Uff. Przejdźmy do przykładów, zobaczymy jaśniej. Wróćmy do naszej wcześniejszej pętli for:

for (var i=0; i<n; i++){ say("Jestem marchewką"); }

Jeśli zanotujemy f maksymalną liczbę operacji wykonanych przez ten fragment kodu, zobaczymy, że f(n) było w przybliżeniu równe 30 x n plus mały koszt pętli. Rzeczywiście, instrukcja say jest powtarzana n razy, co ma stały koszt 30 operacji. Można zatem powiedzieć, że f jest zdominowane przez funkcję g(n)=n. Zatem mamy f(n)=O(n). Mówimy również, że ten fragment kodu jest „w O(n)”.

A funkcja przecięcia tablic o rozmiarze n? Widzieliśmy, że z grubsza zużywa n² x (liczba operacji wypychania + koszt porównania dwóch elementów). Zakładając, że koszt wypychania jest stały (co jest fałszywe, ale nie chcę od razu wchodzić w szczegóły), ustalając K = (liczba operacji wypychania + koszt porównania dwóch elementów), mamy, że koszt funkcja przecięcia jest zdominowana przez n²: mówimy, że funkcja przecięcia jest „w O(n²)”.

Zatem notacja O umożliwia zmierzenie wzrostu kosztu w zależności od wielkości danych wejściowych: funkcja przecięcia będzie miała koszt, który rośnie „z tą samą prędkością” co n² (przy n rozmiarze tablic).

Zainteresowanie Leekwars

To pojęcie jest interesujące, ponieważ często możemy dość łatwo oszacować O(g(n)), a tym samym wiedzieć, czy funkcja zacznie kosztować bardzo drogo, gdy dane wejściowe wzrosną. Jest to na przykład uti