ALG"8

228 Rozdział 9. Zaawansowane techniki programowania

• funkcja KOMB polega na najzwyklejszym porównywaniu wyników cząstkowych - jej rolę pełnią instrukcje oznaczone w' komentarzach przez (1) i (2).

W dalszych przykładach nic będziemy już tak dokładnie „rozbierać” procedur, ufamy bowiem, że Czytelnik w miarę potrzeby uczyni to bez trudu samodzielnie.

Obliczenie złożoności obliczeniowej procedury min max2 także nie nastręcza trudności. Dekompozycja problemu jest następująca:

7 (/z) —) 2 + 7]

2 + 271

Jest to znany nam już rozkład logarytmiczny, po rozwiązaniu otrzymamy wynik T(n) e O(n) (patrz §3.7.3).

Obliczenie złożoności praktycznej T(n) tego programu nie należy do trudnych. Jeśli odpowiednio rozpiszemy równanie:

T(n) = 2 l 27’^j = 2 + 2j 2 + 7^ jj = etc.

i założymy, że istnieje pewne k, takie że n=2^k, to otrzymalibyśmy takie samo równanie, jak w przypadku procedury min mml. Nie powinno to budzić zdziwienia, biorąc pod uwagę, że w drugiej wersji wykonujemy dokładnie taką samą pracę, jak w poprzedniej - postępując jednak w odmienny sposób.

Czy powyższy wynik nie jest czasem nieco niepokojący? Wygląda bowiem na to, że nowa metoda nie gwarantuje poprawy efektywności algorytmu!

Trafiliśmy już na zapowiedziany we wstępie przypadek problemu, dla którego zastosowanie metody „dziel-i-rządź” nic zmienia w istotny sposób parametrów „czasowych” programu. Cóż, można się przynajmniej łudzić, że ich nie pogarsza! Niestety, w naszym przypadku nie jest to prawdą. Jeśli sięgniemy pamięcią do rozdziału poświęconego rekurencji i jej „ciemnym stronom” powinno być dla nas jasne, że z uwagi na wprowadzenie dodatkowego obciążenia pamięci (stos wywołań rekurencyjnych) i niepomijalnej ilości dodatkowych wywołań reku-rencyjnych zakładana równoważność „czasowa” obu procedur nic jest prawdą.

Przedstawiony powyżej przykład nie jest prawdopodobnie najlepszą reklamą omawianej metody - miał on jednak na celu ukazanie potencjalnych zagrożeń związanych z naiwną wiarą w „cudowne metody”. Są oczywiście przypadki, w których „dziel-i-rządź” czyni wręcz cuda (już zaraz kilka z nich zresztą zaprezentuję...), ale o ich zaistnieniu można się przekonać jedynie wyliczając zło-