Asymptotyczne tempo wzrostu

Jak na razie analizowaliśmy wyszukiwanie liniowe i binarne poprzez liczenie ilości maksymalnych prób, które musimy wykonać. Lecz to, co chcemy tak naprawdę wiedzieć to, jak długo się wykonuje. Jesteśmy zainteresowani czasem wykonania, nie tylko ilością prób. Czas wykonania wyszukiwania liniowego oraz binarnego obejmuje czas poświęcony na wykonanie i sprawdzenie każdej próby, oprócz tego związany jest jeszcze z czymś więcej niż tylko z tymi czynnościami.

Czas wykonania algorytmu zależy od tego, jak szybko komputer jest w stanie wykonać instrukcje, zawarte w kodzie danego algorytmu. A to zależy od szybkości komputera, języka programowania oraz kompilatora, który tłumaczy program z języka programowania na kod, który wykonywany jest bezpośrednio na komputerze jak również innych czynników.

Przyjrzyjmy się czasowi wykonania algorytmu bardziej dokładnie. Po pierwsze, określmy jak długo wykonuje się algorytm w odniesieniu do rozmiaru danych wejściowych. Ta koncepcja jest dość intuicyjna, nieprawdaż? Już wiemy, że maksymalna liczba prób w wyszukiwaniach liniowym oraz binarnym zwiększa się wraz ze wzrostem długości przeszukiwanej tablicy. Pomyśl sobie o systemie GPS. Jeśli znałby tylko o autostrady, a nie każdą najmniejszą drogę, wyznaczenie trasy byłoby znacznie szybsze, prawda? Więc o czasie wykonania algorytmu myślimy, jako funkcji wielkości danych wejściowych.

Druga ważna idea polega na tym, że skupiamy się na pytaniu, jak szybko funkcja ta rośnie wraz ze wzrostem wielkości danych wejściowych. Mówimy na to tempo wzrostu czasu wykonania. Aby móc wykonać obliczenie, upraszczamy badaną funkcję, by wydobyć z niej najważniejsze elementy, odrzucając te mniej istotne. Załóżmy, na przykład, że algorytm działa na rozmiarze danych wejściowych wynoszącym $n$‍, i wówczas zajmie mu to $6n^2+100n+300$‍ instrukcji maszynowych. Wyraz $6n^2$‍ zaczyna gwałtownie rosnąć, gdy staje się większy od $100n+300$‍, to znaczy, gdy $n=20$‍). Poniżej znajduje się wykres przedstawiający wartości dla $6n^2$‍ oraz $100n+300$‍ dla $n$‍ od 0 do 100.

Mówimy, że czas działania tego algorytmu rośnie jak $n^2$‍, pomijając współczynnik 6 oraz pozostałe wyrażenia $100n+300$‍. Tak naprawdę nie ma to znaczenia, jakich współczynników używamy; tak długo jak czas wykonania wynosi $a{n}^2+bn+c$‍, dla niektórych liczb $a>0$‍, $b$‍ oraz $c$‍ zawsze będą wartością $n$‍, dla których $a{n}^2$‍ jest większe niż $bn+c$‍ i ta różnica zwiększa się wraz ze wzrostem $n$‍. Na przykład, poniżej znajduje się wykres ilustrujący wartości dla $0,6n^2$‍ oraz $1000n+3000$‍, gdzie dokonaliśmy redukcji współczynnika $n^2$‍ 10-krotnie natomiast pozostałe dwie stałe zwiększyliśmy 10-krotnie.

Wartość $n$‍, przy którym $0,6n^2$‍ staje się większe od $1000n+3000$‍ wzrosła, ale zawsze znajdzie się punkt przecięcia bez względu na to, jakie przyjęte stałe.

Dzięki pominięciu mniej znaczących wyrażeń i stałych współczynników, możemy skupić się tej części algorytmu, która w największym stopniu wpływa na czas jego wykonania – jest to tempo wzrostu – bez pogrążania się w szczegóły, które utrudniają jego zrozumienie. Kiedy pomijamy stałe współczynniki oraz mniej znaczące wyrażenia, używamy notacji asymptotycznej. Zapoznamy się z jej trzema postaciami: notacja duże-$\mathrm{\Theta }$‍, notacja duże-O oraz notacja duże-$\mathrm{\Omega }$‍.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormen i Devina Balkcom oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.