Złożoność algorytmu zdefiniowaliśmy jako funkcję rozmiaru danych. Istotną informacją zawartą w tej funkcji jest jej zachowanie asymptotyczne, gdy rozmiar danych dąży do nieskończoności. Jest rzeczą zrozumiałą, że dla danych niewielkich rozmiarów, metoda obliczeń nie jest tak ważna, jak dla dużych danych, gdy nawet drobne zmiany wielkości danych powodują ogromne zmiany w poniesionym koszcie.

Co więcej, dla dużych n nie jest też istotne, czy algorytm wykonuje n, czy n+5 operacji dominujących. Nawet stały współczynnik nie ma wielkiego znaczenia: jeśli jakiś algorytm wykonuje n² operacji, a inny 2n², to ich szybkość wzrostu do nieskończoności jest w przybliżeniu taka sama.

Definicja 6.1 Notacja asymptotyczna, wielkie O.

Niech f i g będą dwoma funkcjami ze zbioru liczb naturalnych w zbiór liczb rzeczywistych dodatnich, f, g : N ® R⁺. Powiemy, że funkcja g jest co najwyżej rzędu f, w skrócie g = O(f), wtedy i tylko wtedy, gdy dla pewnej stałej c i dla prawie wszystkich n, wartości funkcji g można oszacować z góry przez wartości funkcji f pomnożone przez stałą c,

g = O(f) wttw ($c>0)($n₀ÎN)("n>n₀) g(n) £ c ´ f(n)

Rozważmy dla przykładu trzy funkcje f(n) = 10^-6 n , g(n) = 10⁶ n + 1000, h(n) = n² + 3n +1. Na mocy przyjętej definicji, zarówno funkcję f jak i funkcję g można oszacować z góry przez funkcję liniową n,

Obie równości są spełnione dla dowolnych liczb naturalnych i, na przykład, dla stałej c=1, w pierwszym przypadku, a stałej c=2´10⁶, w drugim przypadku. Funkcji h nie można oszacować z góry przez funkcję g, gdyż zawsze znajdzie się dostatecznie duże n, że wartość h(n) będzie większa niż g(n), niezależnie od wyboru stałej c. Rzeczywiście, jeśli ustalimy c>0, to dla n > (c+1)10⁶ mamy

Obie funkcje f i g można natomiast oszacować z góry przez funkcję h: funkcja kwadratowa rośnie do nieskończoności szybciej niż dowolna funkcja liniowa.

10^-6 n < 10⁶ n + 1000 < 10⁶ (n+1) < n(n+1) < c (n² + 3n + 1 ) dla stałej c=1 i dla n> 10⁶ .

Wszystkie trzy funkcje można też oszacować przez dowolny wielomian rzędu wyższego niż 1. Oczywiście, im wyższy stopień tego wielomiany, tym mniej dokładne jest to oszacowanie.

Zauważmy, że dla dużych n, ani stały składnik, ani nawet stały współczynnik multiplikatywny nie mają wielkiego znaczenia. Jeśli jakiś algorytm wykonuje c₁´ n + c₂ operacji, a inny n², to niezależnie od stałych c₁ i c₂, algorytm o złożoności c₁´n + c₂ będzie lepszy dla dostatecznie dużych n.

Zauważmy jeszcze proste własności notacji asymptotycznej, które przydadzą się nam przy szacowaniu kosztów algorytmów omawianych w tym wykładzie.

Lemat 6.1

Dla dowolnych funkcji f, g, h określonych w zbiorze liczb naturalnych i o wartościach w zbiorze liczb rzeczywistych dodatnich,

jeżeli f = O(g) i g = O(h), to f = O(h),
jeżeli f = O(h) i g = O(h), to f + g = O(h),
jeżeli f = O(h), to c´f = O(h), dla dowolnej stałej c>0.

Dowód lematu wynika natychmiast z definicji notacji wielkie O. Rozważmy dla przykładu drugą własność. Niech f=O(h) i g = O(h). Istnieją więc dodatnie stałe c1 i c2 oraz liczby naturalne n1 i n2 takie że

Przyjmując jako n₀ = max(n₁, n₂) oraz c = c₁+ c₂, otrzymamy f(n) + g(n) £ c₁´ h(n) + c₂ ´ h(n) = c ´ h(n) dla wszystkich n ³ n₀, co dowodzi, że f + g = O(h).

Analogicznie do oszacowania górnego, wprowadza się oszacowanie dolne asymptotycznego rzędu funkcji.

Definicja 6.2 Notacja asymptotyczna, oszacowanie dolne.

Niech f i g będą funkcjami ze zbioru liczb naturalnych w zbiór liczb rzeczywistych dodatnich, f, g : N ® R⁺. Powiemy, że funkcja g jest co najmniej rzędu f, w skrócie g = W(f), wtedy i tylko wtedy, gdy istnieje dodatnia stała c, że dla prawie wszystkich n, wartości funkcji g można oszacować z dołu przez wartości funkcji f pomnożone przez stałą c,

g = W(f) wttw ($c>0)($n₀ÎN)("n>n₀) c ´ f(n) £ g(n)

Rozważmy jeszcze raz funkcje z poprzedniego przykładu. Jak wynika z poprzednich rozważań, funkcję h(n) = n² + 3n +1 możemy oszacować z dołu przez funkcję g(n) = 10⁶ n + 1000, a tym bardziej przez funkcję f. Nieco wbrew intuicji, funkcję f można oszacować z dołu przez funkcję g przyjmując odpowiednią wartość dla stałej c,

Nie jest natomiast możliwe oszacowanie funkcji g z dołu przez funkcję h. Oczywiście, dla wszystkich k>2 mamy też n^k = O(h(n)).

Definicja 6.3 Rząd funkcji.

Funkcje f i g takie, że f, g : N ® R⁺ mają asymptotycznie ten sam rząd wielkości, co oznaczamy f = Q(g), wtedy i tylko wtedy, gdy

g = O(f) oraz f = O(g).

Na mocy tej definicji każda z funkcji n³+ 100n, 100n³ , (1/100)n³, ( n⁵ +n⁴ +15 n)/ (n² +10n + 6) ma taki sam rząd jak funkcja n³.

Warto zapamiętać, że rzędy wielkości asymptotycznej znanych funkcji: lg n, n, n lg n, n², n³, 2ⁿ, 3ⁿ, nⁿ ściśle rosną: każdą funkcja w tym ciągu może być z góry oszacowana przez funkcję następną, a żadna z nich nie może być z góry oszacowana przez funkcję poprzednią.

Następujący lemat pozwala ustalić asymptotyczny rząd funkcji metodami analizy matematycznej.

Lemat 6.2

Niech f i g będą funkcjami określonymi na liczbach naturalnych, o wartościach w zbiorze liczb rzeczywistych dodatnich, oraz niech lim_n®¥ f(n)/g(n) = c. Wtedy

jeżeli c >0, to funkcje f i g mają asymptotycznie ten sam rząd f = Q(g) i g = Q(f),
jeżeli c = 0, to rząd g jest ściśle większy niż rząd funkcji f, f = O(g) i f ¹ Q(g),
jeżeli c = +¥, to rząd funkcji f jest ściśle większy niż rząd funkcji g, g = O(f) i f ¹ Q(g).

Korzystając z tego lematu łatwo udowodnimy, że funkcja 2ⁿ ma inny rząd niż funkcja 3ⁿ. Chociaż obie rosną do nieskończoności bardzo szybko, to asymptotyczny rząd funkcji 2ⁿ jest ściśle mniejszy niż rząd funkcji 3ⁿ,

Podobnie funkcja lg n! rośnie do nieskończoności wolniej niż funkcja kwadratowa n². Rzeczywiście, ponieważ lgn! może być przedstawiony jako suma lg 1 + lg 2 + ... + lg (n-1) + lg n, zatem mamy oszacowanie

Ponieważ obie funkcje (lg n)/n² i (n lg n)/n² dążą do zera przy n zmierzającym do nieskończoności, zatem lim_n®¥ ( (lg n!)/ n²) = 0, co na mocy lematu dowodzi, że log n! = O(n²) oraz log n! ¹ Q(n²).

Definicja 6.4

Powiemy, że algorytm Alg ma czasową złożoność asymptotyczną

wielomianową, jeżeli T(Alg,n) = Q(n^c) dla pewnego naturalnego c>0,

wykładniczą, jeżeli T(Alg,n) = Q(aⁿ) dla pewnego a>1,

liniową, jeżeli T(Alg,n) = Q(n),

kwadratową, jeżeli T(Alg,n) = Q(n²),

logarytmiczną, jeżeli T(Alg,n) = Q(lg n),

liniowologarytmiczną, jeśli T(Alg,n) = Q(nlg n).

Oczywiście najbardziej pożądane są algorytmy o złożoności liniowej. Nie zawsze jednak jest to możliwe. Złożoność większości przedstawionych w tym wykładzie algorytmów jest wielomianowa. Spotkamy się jednak również z algorytmami o złożoności wykładniczej. Takim algorytmem jest np. algorytm generowania wszystkich permutacji danego ciągu, lub metoda zerojedynkowa badania spełnialności formuł rachunku zdań. Aby zrozumieć jak istotna jest dla nas różnica między złożonością wielomianową a wykładniczą, rozważmy następujące zadanie.

Niech będą dane algorytmy: Alg1 o złożoności T(Alg1, n) = n² i Alg2 o złożoności T(Alg2, n) = 2ⁿ, rozwiązujące ten sam problem. Załóżmy, że wykonują one zadanie o rozmiarze k w czasie t na pewnym komputerze K. Zastanówmy się najpierw w jakim czasie zostanie wykonane przy pomocy tych algorytmów zadanie 5 razy większe. Dla algorytmu Alg1 mamy t ´ (5k)²/ k² = 25t, a dla algorytmu Alg2, t ´ (2^5k)/2^k = t ´ (2^k)⁴ = t⁵, czyli algorytm Alg1 wykona większe zadanie w czasie 25 razy dłuższym, a algorytm Alg2 potrzebuje aż t⁵ czasu. Może się wydawać, że sytuacja zmieni się, jeśli algorytmy będą wykonywane na szybszym, np. 16 razy szybszym, komputerze. Jaki jest maksymalny wymiar zadania, które można rozwiązać na tym komputerze w czasie t. Zadanie o rozmiarze k wykonamy więc 16 razy szybciej, czyli w czasie t/16. Algorytm Alg1 może zatem wykonać w czasie t na szybszym komputerze zadanie o rozmiarze x, gdzie

Pytanie 7: Która z funkcji lg (n²), czy 2^lg(lgn) ma asymptotycznie większy rząd?