4. Analiza złożoności

4.1. Złożoność obliczeniowa i asymptotyczna

Często ten sam problem można rozwiązać za pomocą różnych algorytmów, o różnej efektywności. Różnice między algorytmami mogą być bez znaczenia przy przetwarzaniu małej liczby elementów, ale rosną one proporcjonalnie do rozmiaru danych. J. Hartmanis i R. E. Stearns wprowadzili pojęcie złożoności obliczeniowej - miary służącej do porównywania efektywności algorytmów.
Złożoność obliczeniowa określa, ilu zasobów wymaga użycie danego algorytmu lub jak jest ono kosztowne. Koszt ten można mierzyć na wiele sposobów, a jego znaczenie wynika z określonego kontekstu. W niniejszej książce zajmujemy się dwoma kryteriami efektywności: czasem i pamięcią. Czynnik czasu jest istotniejszy niż pamięć, więc rozważania dotyczące efektywności zazwyczaj koncentrują się na ilości czasu poświęconego na przetwarzanie danych. Jednak nawet najbardziej nieefektywny algorytm uruchomiony na komputerze Cray może wykonywać się znacznie szybciej niż najefektywniejszy uruchomiony na PC, tak więc czas wykonania programu zawsze zależy od systemu. Żeby można było zatem porównać ze sobą setkę algorytmów, wszystkie one musiałyby być uruchomione na tej samej maszynie. Co więcej, wyniki testów czasu wykonania będą zależały od języka programowania, w jakim dany algorytm został napisany, nawet jeśli testy są przeprowadzane na tej samej maszynie. Program skompilowany wykonuje się znacznie szybciej niż interpretowany. Program napisany w języku C lub Pascalu może być 20-krotnie szybszy od takiego samego programu zakodowanego w Basicu bądź Lispie.
Do oceny efektywności algorytmu nie należy używać konkretnych jednostek czasu jak mikro- czy nanosekundy. Zamiast nich powinno się stosować jednostki logiczne, wyrażające zależność między rozmiarem n pliku lub tablicy a ilością czasu t potrzebnego do przetworzenia danych. Jeżeli związek między rozmiarem n a czasem t jest liniowy, czyli t#1=cn#1, to 5-krotny wzrost wielkości danych da w efekcie wzrost czasu wykonania o ten sam czynnik; jeśli n#2 = 5n#1, to t#2 = 5t#1. Podobnie, jeśli t#1 = log#2n, to podwojenie n spowoduje zwiększenie t tylko o jedną jednostkę czasu, jeśli bowiem t#2 = log#2(2n), to t#2 = t#1+1
67
Funkcja wyrażająca zależność między n a t jest zwykle dużo bardziej skomplikowana, a jej obliczenie ma znaczenie jedynie w odniesieniu do dużych rozmiarów danych; składniki, które nie zmieniają zasadniczo jej wielkości, powinny zostać odrzucone. Tak otrzymana funkcja daje jedynie przybliżoną miarę efektywności algorytmu. Przybliżenie to jednak jest dostatecznie bliskie oryginałowi, szczególnie jeśli dotyczy przetwarzania dużych porcji danych. Ta miara efektywności nosi nazwę złożoności asymptotycznej i jest stosowana, kiedy pomija się niektóre składniki funkcji dla wyrażenia efektywności algorytmu albo kiedy dokładne obliczenie funkcji jest trudne lub niemożliwe, a można jedynie znaleźć przybliżenie. W celu zilustrowania pierwszego przypadku rozważmy następujący przykład:

(4.1) f(n) = n^2 + 100 n + log#10*n) + 1000

Dla małych wartości n ostatni składnik, 1000, jest największy. Kiedy n wynosi 10, składniki drugi 100n) i ostatni (1000) są równe, a pozostałe wnoszą niewielki wkład do wartości funkcji. Kiedy n osiąga wartość 100, składniki pierwszy i drugi dają taki sam wkład do wyniku. Gdy jednak n przekracza 100, wkład drugiego składnika staje się mniej znaczący. Zatem dla dużych wartości n, z powodu kwadratowej szybkości wzrostu pierwszego składnika (n^2), wartość funkcji f zależy głównie od jego wartości, co widać na rysunku 4.1. Pozostałe składniki mogą być zaniedbane dla dostatecznie dużych n.

n; f(n); n^2; 100n; log#10(n); 1000
puste; wartość; (wartość; %); (wartość; %); (wartość; %); (wartość; %) (uwaga -dla wartości od n^2 do 1000 w dolnej części tabeli liczby będą określały wartość i %)
1; 1101; (1; 0,1) (100; 9,1) (0; 0,0) (1000; 90,82)
10; 2101; (100; 4,76) (1000; 47,6) (1; 0,05) (1000; 47,62)
100; 21002; (10000; 47,6) (10000; 47,6) (2; 0,001) (1000; 4,76)
1000; 1 101003; (1000000; 90,8) (100000; 9,1) (3; 0,0003) (1000; 0,09)
10000; 101 001004; (100000000; 99,0) (1000000; 0,99) (4; 0,0) (1000; 0,001)
100000; 10010001005; (10000000000; 99,9) (10000000; 0,099) (5; 0,0) (1000; 0.00)

Rys. 4.1. Szybkość wzrostu poszczególnych składników funkcji f(n)=n^2+100n+log#10*n)+1000

4.2. Notacja "wielkie O"
Najpowszechniej stosowanym zapisem przeznaczonym do wyrażania złożoności asymptotycznej, czyli szacowania szybkości wzrostu funkcji, jest notacja "wielkie O", wprowadzona w 1894 r. przez Paula Bachmanna. Dla danej pary funkcji f i g o dodatnich wartościach rozważmy następującą definicję:

Definicja 1.f(n) jest O(g(n)), jeśli istnieją liczby dodatnie c i N takie, że f(n)<=cg(n) dla wszystkich n>=N.
68
Definicję czyta się tak: fjest O wielkie od g, jeśli istnieje liczba dodatnia c taka, że f jest nie większa niż cg dla dostatecznie dużych n, to znaczy dla wszystkich n większych niż pewna liczba N. Związek między f a g można wyrazić, mówiąc, że g (n) jest górnym ograniczeniem wartości f(n) (z dokładnością do stałej c) albo że dla dostatecznie dużych n funkcja frośnie nie szybciej niż g.
Problem z powyższą definicją polega na tym, że - po pierwsze - mówi ona, iż muszą istnieć pewne stałe c i N, ale nie sugeruje w żaden sposób, jak je wyznaczyć. Po drugie - nie nakłada żadnych ograniczeń na ich wartości i dostarcza mało wskazówek w sytuacji, kiedy mamy wielu kandydatów na te stałe. W rzeczywistości dla tej samej pary funkcji f i g można zwykle podać nieskończenie wiele odpowiednich par c i N. Na przykład dla

(4.2) f(n)=2n^2+3n+1=O(n^2)

gdzie g(n) = n^2, możliwe wartości c i N są pokazane na rysunku 4.2.
c; >=6; >=(3)3/4; >=(3)1/9; >=(2)13/16; >=(2)16/25; ... -> 2 (uwaga:np. (3)1/9 czytaj trzy całe jedna dziewiąta)
N; 1; 2; 3; 4; 5 -> nieskoń.

Rys. 4.2. Różne wartości c i A/dla funkcji f(n) = f(n)=2n^2+3n+1=O(n^2)O , wyliczone stosownie do definicji wielkiego O.

Wartości te otrzymujemy, rozwiązując nierówność

2n^2 + 3n + 1 <= cn^2
lub równoważnie
2 + 3/n + 1/n^2 <= c

dla różnych n. Pierwszą nierówność otrzymujemy przez wstawienie funkcji kwadratowej z równania 4.2 za f(n) w definicji "wielkiego O", a n^2 za g(n). Ponieważ jest to jedna nierówność z dwiema niewiadomymi, można wyznaczyć różne pary stałych c i N dla tej samej funkcji g(=n^2). Aby wybrać najlepsze c i N, należy wyznaczyć, dla jakich N określony składnik w f staje się dominujący i taki pozostaje. W równaniu 4.2 jedynymi kandydatami na największy składnik są 2n2 i 3/7. Można je porównać za
pomocą nierówności 2n^2>3n, która jest spełniona dla n>1; stąd N=2 i c>=(3)3/4, jak widać z rysunku 4.2.
Jakie jest praktyczne znaczenie wyliczonych właśnie par stałych? Wszystkie są związane z tą samą funkcją g(n)=n^2 i z tą samą funkcją f(n). Dla ustalonego g można dobrać nieskończenie wiele par c i N. Rzecz w tym, że f i g rosną tak samo szybko. Definicja powiada jednak, że funkcja g jest prawie zawsze większa lub równa f jeśli

69

przemnożyć ją przez stałą c. "Prawie zawsze", to znaczy dla wszystkich n nie mniejszych niż stała N. Sedno sprawy tkwi w tym, że wartość c zależy od tego, jakie N zostało wybrane, i odwrotnie. Jeśli na przykład wybierzemy N równe l, czyli cg(n} ma być od razu nie mniejsze niż f. to c musi być równe 6 lub więcej. Jeżeli cg(n) jest większe bądź równe f(n), poczynając od n = 2, to wystarczy przyjąć c równe
3,75. Stała c musi wynosić przynajmniej (3)1/9, jeśli cg(n) ma być nie mniejsze niż
f(n) dla n>=3. Na rysunku 4.3 widać wykresy funkcji f i cg dla różnych wartości współczynnika c. Liczba N jest zawsze wyznaczona przez punkt przecięcia wykresów funkcji cg(n) i f.

Rys. 4.3. Porównanie funkcji dla różnych wartości c i N z rysunku 4.2(wykresy)

Nieodłączny brak precyzji notacji "wielkie O" idzie jeszcze dalej, ponieważ może istnieć nieskończenie wiele funkcji g dla ustalonej funkcji f. Na przykład f z równania 4.2 jest "O wielkie" nie tylko od n^2, ale także od n^3, n^4, ..., n^k,, ... dla dowolnego k większego od 2. Z tego bogactwa możliwości wybieramy najmniejszą funkcję g, tutaj n^2.
Przybliżenie funkcji f można uczynić dokładniejszym, stosując notację "wielkie O" jedynie w części w celu pominięcia nie znaczącej informacji. W równaniu 4.1 na przykład wkład trzeciego i ostatniego składnika do wartości funkcji można pominąć:
(4.3) f(n)=n^2+100n+O(log(#10)n)

Podobnie, funkcję/w równaniu 4.2 można przybliżyć jako

(4.4) f(n)=2n^2+O(n)
70

Wreszcie obydwie te funkcje można przybliżyć jako O(n^2), co zaciera wszelkie rozróżnienie między nimi. Przybliżenia w równaniach 4.3

4.3. Własności notacji "wielkie O"

Notacja ,, wielkie O" ma kilka pożytecznych własności, które można wykorzystać przy szacowaniu efektywności algorytmów.
Własność 1. (przechodniość) Jeśli f(n) jest O(g(n)) i g(n) jest O(h(n)), to f(n) jest O(h(n)). (Inaczej mówiąc O(O(g(n))) jest O(g(n))).

Dowód: Zgodnie z definicją, f(n) jest O(g(n)), jeśli istnieją liczby dodatnie c#1 i N#1 takie, że f(n)<=c#1[g(n)] dla wszystkich n>=N#1, a g(n) jest O(h(n)) jeśli istnieją liczby dodatnie c#2 i N#2 takie, że g(n)N#2.

Stąd c#1[g(n)]<=c#1*c#2*h(n) dla n>=N, gdzie N jest większą z liczb N#1, i N#2. Jeśli przyjmiemy c = c#1*c#2, to f(n)<=ch(n) dla n>N, co oznacza, że f jest O(h).

Własność 2. Jeśli f(nt) jest O(h(n)) i g(n) jest O(h(n)), to f(n) + g(n) jest O(h(n)).
Dowód: Jeśli weźmiemy c równe c#1+c#2, to f(n)+g(n)<=ch(n).

Własność 3. Funkcja an^k jest O(n^k).
Dowód: Wystarczy przyjąć c>a.

Własność 4. Funkcja n^k jest O(n^(n+j)) dla dowolnego dodatniego j.
Dowód: Nierówność jest spełniona dla c = N = 1 .

Z wszystkich tych własności wynika, że dowolny wielomian jest ,,O wielkie" od n podniesionego do najwyższej w nim potęgi, czyli
f(n)=a#k*n^k+a#(k-1)*n^(k-1)+...+a#1*n+a#0 jest O(n^k)
Jest też oczywiste, że dla wielomianów funkcji f(n) jest O(n^(k+j)) dla dowolnego dodatniego j.
Jedną z najważniejszych funkcji przy ocenianiu efektywności algorytmów jest funkcja logarytmiczna. Jeżeli można wykazać, że złożoność algorytmu jest rzędu logarytmicznego, algorytm można traktować jako bardzo dobry. Istnieje nieskończenie wiele funkcji lepszych w tym sensie niż logarytmiczna, jednak zaledwie kilka spośród nich, jak O(lg lg)n)) czy O(1), ma praktyczne znaczenie. Zanim udowodnimy ważną własność dotyczącą funkcji logarytmicznych, sformułujmy oczywistą własność:


71

Własność 5. Jeśli f(n) = cg(n), to f(n) jest O(g(n)).

Własność 6. Funkcja log#a(n) jest O(log#b(n)) dla dowolnych a i b większych niż 1.

Wspomniana wyżej zależność zachodząca między funkcjami logarytmicznymi mówi, że niezależnie od podstawy logarytmu dwie funkcje logarytmiczne są "0 wielkie" jedna od drugiej i że wszystkie takie funkcje rosną tak samo szybko.
Podstawiając log#a(n)=x i log#b(n)=y, z definicji logarytmu mamy a^x=n i b^y=n.
Zlogarytmowanie obu stron daje
xln a = ln n i ylog#a(n) = ln n

Zatem

xln a = yln b
ln a*log#a(n)=log#a(n)*log#b(n)
log#a(n)=ln b/(ln a)*log#b(n)=clog#b(n)

co dowodzi, że log#a(n) i log#b(n) różnią się czynnikiem multiplikatywnym. Na mocy własności 5 log$a(n) jest 0(log n).
Ponieważ podstawa logarytmu nie ma znaczenia w kontekście notacji "wielkie 0", można ją opuszczać, a własność 6 można sformułować następująco:

Własność 7. log#a(n) jest 0(lg n) dla dowolnego dodatniego a, gdzie lg n = log#2(n).

4.4. Notacje Omega i Teta( uwaga:w książce jako sduże greckie litery)
Notacja "wielkie 0" odnosi się do górnych ograniczeń funkcji. Istnieje symetryczna definicja dotycząca dolnych ograniczeń:

Definicja 2. f(n) jest Omega(g(n)), jeśli istnieją liczby dodatnie c i N takie, że f(n)>=cg(n) dla wszystkich n>=N.

Definicję czyta się tak: f jest omega wielkie od g, jeśli istnieje liczba dodatnia c taka, że f jest równa co najmniej cg(n) dla prawie wszystkich n. Innymi słowy, cg(n) jest dolnym ograniczeniem f(n) albo dla dostatecznie dużych n funkcja f rośnie przynajmniej tak szybko jak g.

72

Jedyna różnica między tą definicją a definicją "wielkiego O" to znak nierówności; jedna definicja przechodzi w drugą, gdy zastąpimy znak ">" znakiem ,,<". Związek między obiema notacjami wyraża się równoważnością
f(n) jest Omega(g(n)} wtedy i tylko wtedy, gdy g(n) jest O(f(n))
W notacji Omega pojawia się ten sam problem nadmiaru, co w notacji "wielkie O":
istnieje nieskończenie wiele sposobów wyboru stałych c i N. Dla równania 4.2 można
przyjąć te same wartości kandydatów co na rysunku 4.2, tyle że wszystkie znaki
>= muszą być zastąpione przez <= . Poza tym, jeśli g jest OMEGA od F, a h >= g, to h jest Omega od f;
jeśli dla f możemy znaleźć jedno g będące Omega od f to możemy ich znaleźć nieskończenie wiele. Na przykład n^2 jest Omega od funkcji 4.2, a także od n, n^2, n^3, n^4, ... oraz lg n,lg*lg n i wielu innych funkcji. Dla celów praktycznych najbardziej interesujące są najbliższe, największe z dolnych ograniczeń. Taki wybór czynimy niejawnie za każdym razem, gdy wybieramy Omega dla danej funkcji f.
Istnieje nieskończenie wiele dolnych ograniczeń funkcji f (podobnie jak i górnych); zbiór funkcji g takich, że f(n) jest Omega(g(n)), jest nieskończony. Może to być nieco niepokojące, więc ograniczamy naszą uwagę do najmniejszych górnych i największych dolnych ograniczeń. Zauważmy, że istnieje wspólna podstawa dla notacji "wielkie O" i Omega. W definicji "wielkiego O" występuje symbol ,,<=", w definicji Omega symbol ">="; znak ,,=" zawiera się w obydwu nierównościach. Sugeruje to sposób zawężenia zbioru możliwych dolnych i górnych ograniczeń i prowadzi do następującej definicji notacji Teta:

Definicja 3. f(n) jest Omega(g(n)), jeśli istnieją liczby dodatnie c#1, c#2 i N takie, że c#1*g(n)<=f(n)<=c#2*g(n) dla wszystkich n>N.

Definicję czyta się tak:fjest rzędu wielkości g albo inaczej: obie funkcje rosną tak samo szybko dla dostatecznie dużych n. Widać, że f(n) jest Teta(g(n)) wtedy i tylko wtedy, gdy f(n) jest O(g(n)) oraz f(n) jest Omega(g(n)).
Jedyną funkcją spośród wymienionych wyżej, która jest zarówno ,,O wielkie", jak i Omega. od funkcji 4.2, jest n^2. Nie jest to jedyny wybór i nadal istnieje nieskończenie wiele możliwości, bo 2n^2, 3n^2, 4n^2,... są również Teta od funkcji 4.2. Jest jednak raczej jasne, że wybierzemy najprostszą z nich, czyli n^2.
Przy stosowaniu którejkolwiek z powyższych notacji (wielkie O, Omega. i Teta) nie należy zapominać, że są one przybliżeniami ukrywającymi pewne szczegóły, które w wielu sytuacjach mogą się okazać ważne.

4.5, Możliwe problemy

Celem wprowadzonych wcześniej sposobów zapisu (notacji) jest porównanie efektywności rozmaitych algorytmów zaprojektowanych do rozwiązywania tego samego

73

problemu. Jeśli jednak będziemy stosować jedynie notację "wielkie O" do reprezentowania złożoności algorytmów, to niektóre z nich możemy zdyskwalifikować pochopnie. Problem polega na tym, że z definicji tej notacji f jest O(g), jeśli nierówność f(n)Załóżmy, że mamy dwa algorytmy rozwiązujące pewien problem, a wykonywana przez nie liczba operacji to odpowiednio 10^8*n i 10n^2 Pierwsza funkcja jest O(n}, druga O(n^2). Opierając się na informacji dostarczonej przez notację "wielkie O", odrzucilibyśmy drugi algorytm, ponieważ jego funkcja kosztu rośnie zbyt szybko. To prawda, ale dopiero dla odpowiednio dużych n, ponieważ dla n <= 10^7, czyli dziesięć milionów, drugi algorytm wykonuje mniej operacji niż pierwszy. Chociaż dziesięć milionów nie jest niewyobrażalną liczbą elementów do przetworzenia przez algorytm, najczęściej jednak rozmiar danych jest znacznie mniejszy, a wtedy drugi algorytm jest lepszy.
Z tych powodów warto by stosować notację, która uwzględnia stałe zbyt duże z praktycznego punktu widzenia. Udi Manber do oznaczania takich funkcji proponuje notację "podwójneO" (OO): F jest OO(g(n)), jeśli jest O(g(n)), a stała c jest zbyt duża, by mieć praktyczne znaczenie. Zatem 10^8*n jest OO(N). Definicja pojęcia "zbyt duże" zależy jednak od konkretnego zastosowania.
4.6. Przykłady rzędów złożoności

Algorytmy można klasyfikować ze względu na ich złożoność czasową lub pamięciową i w związku z tym można wyróżnić wiele klas algorytmów, co ilustruje rysunek 4.4. Szybkość wzrostu ich funkcji złożoności widać na rysunku 4.5. Na przykład, algorytm nazywamy stałym, jeśli jego czas wykonania pozostaje taki sam niezależnie od liczby przetwarzanych elementów; nazywamy go kwadratowym, jeśli jego czas wykonania wynosi O(n^2). Dla każdej z tych klas pokazana jest liczba operacji oraz faktyczny czas potrzebny do wykonania algorytmu na maszynie mogącej wykonywać milion operacji na sekundę, czyli jedną operację na mikrosekundę. Na rysunku 4.4 widać, że pewne źle zaprojektowane lub nie dające się przyspieszyć algorytmy nie mają praktycznego zastosowania na dostępnych dziś komputerach. Aby przetworzyć milion elementów za pomocą algorytmu kwadratowego, potrzebujemy ponad jedenaście dni, a dla algorytmu sześciennego - tysiące lat. Gdyby nawet komputer mógł wykonywać jedną operację na nanosekundę (miliard operacji na sekundę), algorytm kwadratowy zakończyłby obliczenia po 16,7 s, a sześcienny potrzebowałby nadal ponad 27 lat. Nawet 1000-krotne przyspieszenie pracy ma bardzo mały wpływ na możliwość jego praktycznego zastosowania.



















74
TABELA

klasa; złożoność II liczba operacji i czas wykonania (1 instrukcja/mikrosec;mikrosec - oznaczę "mis") (znakiem II odzieliłem kolumny)

n: II 10; 10^2; 10^3; 10^4; 10^5; 10^6

stały; O(1) II 1 - 1mis; 1 - 1mis; 1 - 1mis; 1 - 1mis; 1 - 1mis; 1 - 1mis
logarytmiczny;O(lg n) II 3,32 - 3mis; 6,64 - 7mis; 9,97 - l0mis; 13,3 - 13mis; 16,6 - 17mis; 19,93 - 20mis
liniowy; O(n) II 10 - 10 mis; 10^2 - 100mis; 103 - 1ms; 104 - 10 ms; 105 - 0,1s; 10^6 - 1s
O(n Ig n); O(n Ig n) II 33,2 - 33mis; 664 - 664mis; 9970 - 10ms; 133*10^3 - 133 ms; 166*10^4 - 1,6s; 199,3*10^5 - 20s
kwadratowy; O(n^2) II 10^2 - 100mis; 1O^4 - 10 ms; 10^6 - 1s; 0^8 - 1,7 min; 10^10 - 16,7min; 10^12 - 11,6dni
sześcienny; O(n^3) II 10^3 - 1 ms; 10^6 - 1s; 10^9 - 16,7 min; 0^12 - 11,6 dni; 10^15 - 31,7lat; 10^18 - 27 397lat
wykładniczy;O(2^n) II 1024 - 10 ms; 10^30 - 3,17*10^16lat; 10^301-puste;10^3010-puste; 10^30103-puste; 10^301030-puste

Rys. 4.4. Klasy algorytmów i ich czasy wykonania na komputerze działającym z szybkością miliona operacji na sekundę
(1s = 10^6mis = 10^3 ms)
Analiza złożoności algorytmów jest rzeczą niezmiernie istotną i nie można jej lekceważyć, argumentując, że żyjemy w czasach, gdy kupiony za stosunkowo niewielką kwotę komputer na naszym biurku potrafi wykonywać miliony operacji na sekundę. Znaczenia analizy złożoności algorytmów w żadnym aspekcie, a szczególnie w kontekście struktur danych, nie sposób przecenić. Imponująca szybkość komputerów nie na wiele się zdaje, jeśli uruchamiane na nich programy używają nieefektywnych algorytmów.

Rys. 4.5. Typowe funkcje stosowane w oszacowaniach z użyciem notacji "wielkie O"{Na rys. przedstawione wykresy funkcji:y=1; y=lg n; y=n; y=n*lg n; y=n^2; y=n^3)


75

4.7. Znajdowanie złożoności asymptotycznej: przykłady

Efektywność algorytmów ocenia się przez oszacowanie ilości czasu i pamięci potrzebnych do wykonania zadania, dla którego algorytm został zaprojektowany. W tym podrozdziale pokazujemy, jak wyznaczać tę asymptotyczną złożoność.
Najczęściej jesteśmy zainteresowani złożonością czasową, mierzoną zazwyczaj liczbą przypisań ł porównań realizowanych podczas wykonania programu. W rozdziale 11, dotyczącym algorytmów sortowania, będziemy rozważać obydwa typy operacji; obecnie skoncentrujemy się jedynie na liczbie instrukcji przypisania.
Zacznijmy od prostej pętli realizującej obliczanie sumy liczb w tablicy:

for ( i = sum = 0 ; i < n; i++)
sum += a[i] ;

Powyższa pętla for powtarza się n razy, a podczas każdego jej przebiegu są wykonywane dwa przypisania: jedno aktualizujące zmienną sum, a drugie zmienną i. Mamy zatem 2n przypisań podczas całego wykonania pętli; jej asymptotyczną złożoność wynosi O (n).
Złożoność zazwyczaj rośnie, gdy używamy pętli zagnieżdżonych, jak w poniższym kodzie, który powoduje wypisanie sumy wszystkich podtablic zaczynających się od pozycji zerowej:

for (i = 0; i < n; i++) {
for ( j = 1 , sum = a[0] ; j <= i ; j++)
sum += a[j];
printf ( " suma dla podtablicy od 0 do %d wynosi %d\n " , i , sum) ;
}

Na samym początku zmiennej i jest nadawana wartość początkowa. Pętla zewnętrzna przebiega n razy, a w każdej jej iteracji wykonuje się wewnętrzna pętla for, instrukcja wypisywania oraz przypisania wartości zmiennym i, j oraz sum. Pętla wewnętrzna wykonuje się i razy dla każdego i należy do {1, ..., n-1}, a na każdą iterację przypadają dwa przypisania: jedno do sum oraz jedno do j. Mamy zatem 1 + 3n + Sigma#i=1;^n-1[2i] = 1 + 3n + 2(1 + 2 + ... + n - 1) = 1 + 3n + n(n - 1) = O(n) + O(n^2) = O(n^2) przypisań wykonywanych w całym programie.
Pętle zagnieżdżone mają zwykle większą złożoność niż pojedyncze, jednak nie musi tak być zawsze. Jeśli na przykład chcemy wypisywać sumy ostatnich pięciu elementów podtablic zaczynających się od pozycji zerowej, możemy zaadaptować powyższy kod i przekształcić go w taki:

76

for (i = 4; i < n; i++) {
for (j =i-3, sum = a[i-4]; j <= i ; j++)
sum += a[j];
printf ( " suma dla podtablicy od %d do %d wynosi %d\n" , i-4 , i , sum) ;
}

Dla każdego i pętla wewnętrzna wykonuje się tylko 4-krotnie; w każdym przebiegu pętli zewnętrznej mamy jedenaście przypisań. Liczba ta nie zależy od rozmiaru tablicy. Program wykonuje łącznie 1 + 11(n - 4) = O(n) przypisań, chociaż wystąpienie pętli zagnieżdżonych sugerowałoby co innego.
Analiza tych dwóch przykładów była stosunkowo prosta, ponieważ liczba obrotów pętli nie zależała od wartości elementów tablicy. Wyznaczenie złożoności asymp-totycznej jest trudniejsze, jeśli liczba iteracji nie jest zawsze jednakowa. Zilustrujemy to za pomocą pętli znajdującej najdłuższą podtablicę zawierającą liczby uporządkowane rosnąco. Na przykład dla [1 8 1 2 5 0 11 12] taką podtablicą jest [l 2 5]. Kod wygląda następująco:

for (i = 0, length = 1; ifor (ii = 12 = k = i; k < n-1 && a[k] < a[k+1]; k++, 12++) ;
if (length < 12 - ii + 1)
length = 12-11 + 1;
}

Zauważmy, że jeśli liczby w tablicy są uporządkowane malejąco, to pętla zewnętrzna wykonuje się n-1 razy, a w każdym jej przebiegu pętla wewnętrzna wykona się tylko raz. Algorytm zatem działa tutaj w czasie O(n). Gorzej jest, kiedy liczby są uporządkowane rosnąco. Wówczas zewnętrzna pętla for wykonuje się n- 1 razy, ale w jej i-tym przebiegu pętla wewnętrzna wykona się i razy dla i należy {l, ..., n-1}. Złożoność algorytmu będzie więc O(n^2). Z reguły dane nie są uporządkowane i oszacowanie efektywności algorytmu jest wtedy rzeczą bardzo istotną. Wyznaczenie złożoności w średnim przypadku jest jednak niełatwym zadaniem. Nie będziemy teraz analizować złożoności dla losowego uporządkowania w naszym przykładzie, ale zajmiemy się taką analizą bardziej szczegółowo w rozdziale 11.
Powyższy przykład wskazuje na potrzebę rozróżnienia przynajmniej trzech przypadków, dla których należy wyznaczyć złożoność algorytmów. Z przypadkiem najgorszym (pesymistycznym) mamy do czynienia wówczas, gdy algorytm musi wykonać maksymalną liczbę kroków, z najlepszym (optymistycznym) - gdy niezbędna liczba kroków jest najmniejsza, a przypadek średni mieści się między tymi dwiema skrajnościami. Rozpoznanie tych przypadków nie zawsze jest łatwe, a muszą one być wyznaczone dla każdego algorytmu. Również znalezienie złożoności w poszczególnych przypadkach bywa wymagającym zadaniem. Zwykle najtrudniejsza do wyliczenia jest złożoność średnia. Jeśli obliczenia są bardzo skomplikowane, to stosuje się przybliżenia, w których przydają się notacje wielkie O,Omega i Teta.

77

4.8. Ćwiczenia

1. Zakładając, że f#1(n) jest O(g#1(n)) i F#2(n) jest 0(g#2(n)), udowodnij następujące stwierdzenia:
(a) f#1(n)+f#2(n) jest O(max(g#1(n),g#2(n)));
(b) jeśli istnieje liczba k taka, że dla n>k g#1(n)<=g#2(n), to O(g#1(n)) + O(g#2(n)) jest 0(g#2(n));
(c) f#1(n) *f#1(n) jest O(g#1(n)*g#2(n)) (zasada iloczynu);
(d) O(cg(n)) jest O(g(n));
(e) c jest O(1).

2. Udowodnij, że

(a) Sigma#i=1;^2[i^2] jestO(n^3) i ogólniej Sigma#i=1;^n[i^k] jestO(n^k+1);
(b) an^k/lg n jest 0(n^k), ale nie Teta(n^k);
(c) n^1,1 + n lg n jest Teta(n^1,1);
(d) 2^n jest O(n!), a n! nie jest O(2^n).

3. Przy tych samych założeniach co w zadaniu 1l, znajdź kontrprzykłady obalające następujące stwierdzenia:
(a) f#1(n)+f#2(n) jest O(g#1(n)-g#2(n));
(b) f#1(n)/f#2(n) jest O(g#1(n)/g#2(n)).

4. Znajdź funkcje f#1 i f#2 takie, że zarówno f#1(n) jak f#2(n) jest O(g(n)), ale f#1(n) nie jest O(f2(n))

5. Przedstawiony w tym rozdziale algorytm znajdowania najdłuższej podtablicy liczb
ułożonych w porządku rosnącym można poprawić, bo nie warto szukać kolejnej podtablicy, jeśli długość najdłuższej z dotychczas znalezionych jest większa niż ilość miejsca do końca tablicy. Zatem jeśli cała tablica była uporządkowana, to przerwiemy poszukiwania od razu, co zmienia najgorszy przypadek w najlepszy. Należy zmienić zewnętrzną pętlę, dokładając jeszcze jeden test:
for (i = 0, length = 1; i < n-1 && length < n - l; i++)
Jaki jest teraz najgorszy przypadek? Czy złożoność w przypadku pesymistycznym wynosi nadal O(n^2)?

6. Wyznacz złożoność poniższych implementacji algorytmów dodawania, mnożenia i transpozycji macierzy n x n.
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i, j] = b[i,j] + c[i, j];

78

for (i = 0; i < n; i++)
for (j = a[i, j] = 0; j < n; j++)
for (k = 0; k < n; k++)
a[i,j]+=b[i,k] * c[k,j];

for (i = 0; i < n - 1; i++)
for (j = i+1; j < n; j++) {
tmp = a[i, j];
a[i, j] = a[j , i];
a[j, i] = tmp;
}

Bibliografia
Złożoność obliczeniowa
[1] Hartmanis J., Hopcroft J. E.: Ań overview of the theory of computational complexity.
Journal of the ACM, 1971, 18, s. 444-475. [2] Hartmanis J., Stearns R.E.: On the computational complexity of algorithms. Transactions of
the American Mathematical Society, 1965, 117, s. 285-306. [3] Preparata Franco P.: Computational complexity. W: Studies in Computer Science, S.V.
Pollack (ed.), The Mathematical Association of America 1982, s. 196-228.
Notacje: wielkie O, Omega. i Teta
[4] Brassard G.: Crusade for a better notation. SIGACT News, 1985, 17, s. 60-64.
[5] Knuth D.: Big omicron and big omega and big theta. SIGACT News, 1976, 8, s. 18-24.
[6] Knuth D.: The art of computer programming. Vol. 2: Seminumerical Algorithms. Reading,
MA, Addison-Wesley 1973. [7] Yitanyi P.M.B., Meertens L.: Big omega versus the wild functions. SIGACT News, 1985,
16, s. 56-59.
Notacja OO
[8] Manber U.: Introduction to Algorithms. A Creative Approach. Reading, MA, Addison--Wesley 1989.