ALG#3

9.1. Programowanie typu „dziel-i-rządf 233

nięciami bitowymi¹. Aby wyliczyć klasę tego algorytmu można sięgnąć do wzorów podanych w rozdziale 3 albo nie wysilać się zbytnio i dojść do wniosku, że... mamy do czynienia z 0(N²).

Skąd ta pewność? Wynika ona z obserwacji wynikłej podczas analizy procedury min_max: dokonaliśmy podziału problemu, ale w niczym nie zmniejszyliśmy ilości wykonywanej pracy. Cudów zatem nie będzie²! Zanim jednak rozczarujemy się na dobre do metody „dzicl-i-rządź”, popatrzmy na następujące „przepisanie” operacji X*Y w nieco inny sposób niż poprzednio:

X■ Y = AC ■ 2~- + [(A - B)(D-C) + AC + BD]2⁷ + BD.

Mimo nieco bardziej skomplikowanej postaci (patrz algorytm Strassena!) zmniejszyliśmy ilość operacji mnożenia z 4 na 3 (AC i BD występują podwójnie, zatem za drugim użyciem można skorzystać z poprzedniego wyniku). Formuła rekuren-cyjna towarzysząca temu rozkładowi jest identyczna jak w przypadku poprzednim, wystarczy tylko zamienić •/ na 3. Wiedząc to, otrzymujemy natychmiast, że algorytm jest klasy ćż(jV^Ioi!:1) = o(x' ^iq).

Zachęca się Czytelnika do zbadania na różnych przykładach i przy użyciu różnorodnych założeń co do kosztów operacji elementarnych (+, -, przesunięcie bitowe), kiedy istotnie ten algorytm może dać „zauważalne” rezultaty w porównaniu z metodą klasyczną.

9.1.4.Inne znane algorytmy „dziel-i-rzgdź”

Nie eksponując specjalnie tego, już w rozdziałach poprzednich mogliśmy zapoznać się z kilkoma ciekawymi algorytmami, które można zaklasyfikować do metody „dziel-i-rządź".

Programem, który zdecydowanie „króluje” wśród nich, jest niewątpliwie słynny QuickSorl (patrz opis). Oferuje on znaczący wzrost szybkości sortowania i, co najważniejsze, jest przy tym niesłychanie prosty zarówno w zapisie, jak i ideowo.

Omówiony przy okazji rozpatrywania technik derekusyw'acji problem wież Hanoi (patrz rozdział 6) jest również dobrym przykładem inteligentnej dekompozycji

1

   Przypomnijmy, że mnożenie liczby przez potęgę podstawy systemu (2¹. 2^:, 2^!...) jest równoważne przesunięciu jej reprezentacji wewnętrznej o „wykładnik potęgi” miejsc w lewo (/, 2, i...).

2

   Dla niedowiarków dowód matematyczny: T(n) e o(N^l<>8;4) = 6)(.V ■ ).