Złożoność algorytmów zwykle mierzymy liczbą wykonywanych przez algorytm operacji, przy tym na ogół, bierzemy pod uwagę tylko pewne charakterystyczne (np. najbardziej kosztowne) dla algorytmu operacje. Miara ta jest najbardziej interesująca wtedy, gdy jest wyrażona jako funkcja zależna od rozmiaru danych. Na przykład dla algorytmu Hornera opisanego w przykładzie 4.5.1(3), rozmiar danych - to stopień wielomianu, którego wartość obliczamy. Złożoność algorytmu można opisać funkcją T(n) = n, wyrażającą fakt, że dla obliczenia wartości wielomianu stopnia n musimy wykonać n iteracji pętli. Mając taką informację, możemy obliczyć czas potrzebny do obliczenia wartości wielomianu stopnia 100 na dowolnym komputerze: będzie to 100*czas potrzebny do wykonania jednej iteracji na tym komputerze + stała (koszt dwu instrukcji przypisania na początku algorytmu). W gruncie rzeczy, funkcja T ma nam pozwolić określić koszt algorytmu ale niekoniecznie z dokładnością do sekund czy milisekund. Jest rzeczą drugorzędną czy algorytm wykona n czy n+3 operacje. Natomiast jest rzeczą istotną, czy jego złóżoność wyraża się funkcją f(n)=n, czy f(n) = n³, i jak zachowuje się algorytm dla dużych n. Interesuje nas raczej rząd kosztu, szybkość z jaką rośnie do nieskończoności niż konkretne liczby. Złożoność algorytmu będzie używana jako (kryterium) argument za lub przeciw użyciu konkretnego algorytmu.

Przypuśćmy, że mamy do dyspozycji 6 algorytmów o złożoności odpowiednio lg n, n, n², n³ i 2ⁿ. Tabliczka na rysunku 4.6.1 podaje oszacowanie maksymalnego rozmiaru danych, które można rozwiązać algorytmem o ustalonej złożoności w podanym czasie, na komputerze, który wykonuje 10⁶ operacji na sekundę. Na przykład, w czasie 1 sek można rozwiązać przy pomocy algorytmu o złożoności T(n)= n² co najwyżej zadanie o rozmiarze 1000, natomiast algorytmem o złożoności T(n)=2ⁿ można rozwiązać tylko co najwyżej zadanie o rozmiarze 19. Warto też zwrócić uwagę, jak powoli zmieniają się rozmiary zadań ze wzrostem przeznaczonego na ich wykonanie czasu, gdy mamy do czynienia ze złożonością określoną funkcją wykładniczą 2ⁿ. Wartości większe niż 10¹⁰ zostały oznaczone symbolem ∞.

Rys. 4.6.1

W tym paragrafie zajmiemy się porównywaniem szybkości wzrostu wartości f(n) funkcji f : N → R⁺ przy n dążącym do nieskończoności.

Jeśli f = O(g), to funkcja g szacuje z góry wartości funkcji f dla dostatecznie dużych n. Inaczej mówiąc funkcja g szybciej dąży do nieskończoności niż funkcja f. Jeśli f = Ω (g), to funkcja g szacuje wartości funkcji f z dołu dla dostatecznie dużych n, tzn. funkcja g rośnie wolniej do nieskończoności niż funkcja f.

Przykład 4.6.1

1. n²/2 + 5n = O(n²). Rzeczywiście, dla c= 5 i wszystkich n>1, n²/2 + 5n ≤ 5n².
2. n = O(2ⁿ), bo n ≤ 2ⁿ dla wszystkich liczb naturalnych n. Rzeczywiście dla n>1 mamy

n= 2 * 3/2 * 4/3 * ...* n/(n-1)

W powyższej równości, po prawej stronie mamy (n-1) elementów, z których każdy jest ≤ 2. Czyli n ≤ 2^n-1 < 2ⁿ.

3. lg (n+1) = O(n), co wynika natychmiast z (2).
4. lg n! = O(n lg n), ponieważ lg n! = lg(1*...*n) = lg1 + lg 2 +..+lg n ≤ n lg n.
5. lg n! = Ω (n lg n), ponieważ :

Pytanie 4.6.1: Które z podanych zależności są prawdziwe?

1. n²/100 + 500n = O(n)

2. n³/2 + n² = Ω (n³)

3. 2ⁿ = O(2^lgn)

4. n = O(2^lgn)

Następujące twierdzenie pozwala zastosować metody analizy matematycznej do porównywania szybkości wzrostu funkcji.

Dowód twierdzenia pomijamy.

Dla przykładu rozważmy funkcje f(n) = √ n i g(n) = lg n. Ponieważ (lgn)/ √ n przy n dążącym do nieskończoności dąży do 0 (lim_{n → ∞ (}(lgx)/ √ x) = lim_{n → ∞ (}(lgx)'/( √ x)') = lim_{n → ∞} (2/(ln2* √ x)) = 0), zatem na mocy powyższego twierdzenia funkcja lg dąży do nieskończoności wolniej niż funkcja √ , czyli g = O(f) oraz , f ≠ Θ (g).

Zadanie 4.6.1

Porównaj rzędy funkcji f(n) = lg n (logarytm przy podstawie 2) i g(n) = log n (logarytm przy podstawie 10).

Rozwiązanie. Ponieważ dla dowolnych a ≠ 1 i a, b >0, log_a b = log_c b/log_c a, zatem log n = (1/lg10)lg n. Wynika stąd, że log n = Θ (lg n).