Przykład 1.7. Na rysunku 1.6 pokazano graficzne przedstawienie czasu (mierzonego w sekundach)
wykonania programów o różnej złożoności czasowej (kompilowanych tym samym kompilatorem
i uruchamianych na tym samym komputerze). Przypuśćmy, że mamy do dyspozycji 1000 sekund.
Jak duży rozmiar danych zdolny jest w tym czasie przetworzyć każdy z programów?
Jak łatwo odczytać z przedstawionego wykresu, rozmiar problemów możliwych do rozwią-
zywania przez każdy z programów w czasie 1000 sekund jest mniej więcej taki sam. Załóżmy teraz,
że bez żadnych dodatkowych kosztów udało nam się wygospodarować czas 10 razy większy lub,
co na jedno wychodzi, otrzymaliśmy dziesięciokrotnie szybszy komputer. Jak w tej sytuacji zmieni
się maksymalny rozmiar problemu możliwego do rozwiązywania?
7 Określenie „problem rozmiaru n” jest tu wygodnym skrótem określającym „dane rozmiaru n przetwa-
rzane przez program rozwiązujący problem” — przyp. tłum.
32
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
RYSUNEK 1.6.
Złożoność czasowa
czterech programów
Zestawienie widoczne w tabeli 1.3 nie pozostawia żadnych wątpliwości. Przewaga programu
o złożoności O(n) jest wyraźnie widoczna, jego możliwości wzrastają dziesięciokrotnie. Pozostałe
programy prezentują się pod tym względem mniej imponująco, ponieważ wielkość problemów
możliwych do rozwiązywania przez nie wzrasta tylko nieznacznie. Szczególnie program o złożoności
O(2n) zdatny jest do rozwiązywania jedynie problemów o niewielkich rozmiarach.
TABELA 1.3.
Wzrost maksymalnego rozmiaru możliwego do rozwiązania problemu
w rezultacie dziesięciokrotnego przyspieszenia komputera
Złożoność
Komputer
Komputer
Względny przyrost
czasowa T(n)
oryginalny
dziesięciokrotnie szybszy
rozmiaru problemu
100n
10
100
10,0
5n2
14
45
3,2
n3/2
12
27
2,3
2n
10
13
1,3
Można w pewnym sensie odwrócić tę sytuację, porównując czas potrzebny na rozwiązanie
(przez każdy z programów) problemu o rozmiarze dziesięciokrotnie większym (w porównaniu do
tego, jaki rozwiązują one w czasie 1000 sekund).
Z tabeli 1.4 wynika niezbicie, że najszybsze nawet komputery nie są w stanie pomniejszyć znaczenia efektywnych algorytmów.
TABELA 1.4.
Wzrost czasu wykonania programu odpowiadający dziesięciokrotnemu zwiększeniu rozmiaru problemu
Złożoność czasowa T(n)
Rozmiar problemu
Czas wykonania
Względny przyrost
programu (s)
czasu wykonania
100n
100
10 000
10
5n2
140
100 000
100
n3/2
120
1 000 000
1000
2n
100
1030 (≈ 3∗1022 lat)
1029
Dochodzimy tym samym do nieco paradoksalnej konkluzji. Otóż w miarę, jak komputery
stają się coraz szybsze, jednocześnie pojawiają się coraz bardziej złożone problemy (a raczej chęć wykorzystania komputerów do ich rozwiązania). To, w jakim stopniu wzrost mocy obliczeniowej
1.5. OBLICZANIE CZASU WYKONYWANIA PROGRAMU
33
przekłada się na wzrost rozmiaru problemów możliwych do rozwiązania, zależy przede wszystkim
od złożoności czasowej używanych algorytmów. Nieustający postęp technologiczny nie tylko więc
nie zwalnia z poszukiwania efektywnych algorytmów, lecz nadaje mu coraz większe znaczenie! —
nawet jeśli wydawałoby się, że powinno być odwrotnie.
Szczypta soli…
Mimo fundamentalnego znaczenia złożoności czasowej, istnieją przypadki, gdy nie jest ona jedynym
ani też najważniejszym kryterium wyboru algorytmu. Oto kilka przykładowych sytuacji, w których
główną rolę odgrywają inne czynniki.
(1) Jeżeli program ma być użyty tylko raz lub kilka razy bądź ma być wykorzystywany sporadycznie, koszty jego wytworzenia i przetestowania znacznie przewyższać będą koszt związany z jego
uruchamianiem. O wiele ważniejsze od efektywności algorytmu jest wówczas jego poprawne
zaimplementowanie w prosty sposób.
(2) Tempo wzrostu czasu wykonania programu, wyrażone przez notację „dużego O” algorytmu
staje się czynnikiem krytycznym w przypadku asymptotycznym, czyli wtedy, gdy rozmiar pro-
blemu zaczyna zmierzać do nieskończoności. Dla małych rozmiarów istotne stają się współ-
czynniki proporcjonalności (w funkcji złożoności czasowej) — duży współczynnik propor-
cjonalności może „zrekompensować” szybkość wynikającą z małego wykładnika potęgi. Istnieje
wiele algorytmów, np. algorytm Schonhagego-Strassena mnożenia liczb całkowitych [1971],
które pod względem złożoności asymptotycznej są zdecydowanie lepsze od konkurentów, lecz
duże współczynniki proporcjonalności dyskwalifikują je pod względem przydatności do roz-
wiązywania problemów pojawiających się w praktyce.
(3) Skomplikowane algorytmy niełatwo zrozumieć, a tworzone na ich bazie programy są trudne
do konserwacji i rozwijania dla osób, które nie są ich autorami. Jeżeli szczegóły danego algo-
rytmu są powszechnie znane w danym środowisku programistów, można bez obaw algorytm ten
wykorzystywać. W przeciwnym razie może się okazać, że opóźnienia i straty wynikłe z niezro-
zumienia lub, co gorsza, z błędnego zrozumienia algorytmu mogą zniweczyć wszelkie korzyści
wynikające z jego efektywności.
(4) Znane są sytuacje, w których efektywne czasowo algorytmy wymagają znacznych ilości pa-
mięci. Wiążąca się z tym konieczność wykorzystania pamięci zewnętrznych (np. do implemen-
tacji pamięci wirtualnej) może drastycznie obniżyć szybkość realizacji programu, niezależnie