Dodatek A
Obliczenia przybliżone

A.1. Szereg harmoniczny

W niektórych zawartych w tej książce obliczeniach dla liczb harmonicznych używamy oznaczenia H#n. Liczby harmoniczne H#n definiuje się jako sumy częściowe szeregu harmonicznego postaci Sigma#i=1;^n[1/n]. Szereg ten ma bardzo duże znaczenie w analizie algorytmów wyszukiwania i sortowania. Dowodzi się, że

H#n=lg n+gama+1/(2n)-1/(12n^2)+1/(120n^4)-epsilon

gdzie n>=1, 0nieporęczne i dla naszych celów nawet za dokładne. Największy udział w H#n prawie zawsze będzie miał In n, jedyny rosnący składnik w powyższym wzorze. H#n można zatem uważać za O(ln n).

A.2. Oszacowanie funkcji lg(n!)

Najgrubsze przybliżenie funkcji lg(n!) można otrzymać dzięki spostrzeżeniu, że każda liczba w iloczynie
n!=1 *2*...*(n-1)*n jest mniejsza lub równa n. Zatem n!<=n^n (n! = n^n tylko dla n=1), skąd wynika, że lg(n!)Ustaliliśmy właśnie, że lg(n!) jest O(nlgn). Wiemy jednak z rozdziału dotyczącego notacji "wielkie O", że dana funkcja może być "O wielkie" od więcej niż jednej funkcji. Czy lg(n!) można przybliżać funkcją mniejszą niż nlgn, jak na przykład cn lub Ig2n? Teoretycznie jest to możliwe, ponieważ naszą aproksymację wyliczyliśmy, używając jedynie górnego ograniczenia funkcji lg(n!). Najpierw znajdziemy dolne ograniczenie n!.

533

Jeśli w iloczynie n! odpowiednio pogrupujemy czynniki, jak w

P#n = (1*n)(2*(n-1))(3*(n-2))...(i*(n-i+1))..., dla 1<=i<=n/2

to można zauważyć, że takich czynników jest n/2 i n! = P#n dla n parzystych albo też czynników jest
(n+1)/2 in!=P#n! (n+1)/2 dla n nieparzystych. Wykażemy, że każdy czynnik w P#n! jest nie mniejszy niż n, czyli

1<=i<=n/2=>i(n-i+1)>=n (=> oznacza "z tego wynika)

Jest tak, ponieważ

n/2>=i=[i(i-1)]/(i-1)=>i(n-2i+2)>=n

i co łatwo sprawdzić

i>=1(n-2i+2<=(n-i+1)

Szukanym dolnym ograniczeniem jest n^n/2, gdyż n!=P#n!>=n^n/2, a więc lg(n!)>=lgn = O(nlgn). Zakładaliśmy tu, że n jest parzyste. Jeśli n jest nieparzyste, trzeba je podnieść do potęgi (n+1)/2 , co niewiele zmienia.

Funkcję lg(n!) oszacowaliśmy za pomocą jej dolnego i górnego ograniczenia, a wynikiem jest n^n/2<=n!<=n^n, czyli n/(2)lgn<=lg(n!)<=nlgn. Przybliżyliśmy zatem lg(n!) z dołu i z góry funkcjami rzędu nlgn. Wynika stąd, że lg(n!) jest tego samego rzędu co te funkcje, czyli że lg(n!) = Teta(nlgn). Innymi słowy, w każdym algorytmie sortowania za pomocą porównań tablicy rozmiaru n trzeba w najgorszym przypadku wykonać przynajmniej O(nlgn) porównań. Funkcja nlgn przybliża zatem optymalną liczbę porównań w najgorszym przypadku.
Rezultat ten nas jednak nie satysfakcjonuje, dotyczy bowiem jedynie najgorszego przypadku, a przypadki takie zdarzają się rzadko. Przy losowym uporządkowaniu danych z reguły będziemy mieli do czynienia z przypadkiem średnim. Czy średnia liczba porównań może być rzeczywiście mniejsza niż O(nlgn)? Niestety, hipotezę tę trzeba odrzucić, a jej fałszywość udowodnią poniższe obliczenia.
Wykażemy, że w dowolnym drzewie binarnym o m liściach, w którym każdy węzeł wewnętrzny ma dwóch synów, średnia liczba krawędzi na ścieżce od korzenia do liścia jest większa bądź równa lgm.

534

Dla m = 2 mamy lgm= 1; jeśli drzewo to korzeń z dwoma liśćmi, to do każdego z nich prowadzi właśnie jedna krawędź. Załóżmy, że nasze twierdzenie zachodzi dla pewnego m >= 2 i że

Ave#m=(p#1+...+p#m/m)>=lgm

gdzie p#i to liczba krawędzi na ścieżce od korzenia do i-tego liścia. Rozważmy teraz losowo wybrany liść, do którego dołączamy dwóch synów. Dla uproszczenia zapisu przyjmijmy, że liść ten, zmieniony w węzeł wewnętrzny, ma numer m, a długość ścieżki od korzenia do węzła m wynosi p#m. Po dodaniu dwóch nowych liści ich łączna liczba wzrasta o jeden, a długością ścieżki do obydwu dodanych liści jest p#(m+1) =p#(m) + 1 . Czy jest teraz prawdą, że

Ave#m=[p#1+...+p#(m-1)+2p#m+2]/(m+1)]>=lg(m+1)

Z definicji Ave#m i Ave#(m+1) oraz na mocy faktu, że p#m = Ave$m (ponieważ liść m był wybrany losowo), mamy

(m+1)Ave#(m+1)=mAve#(m)+p#m+2=(m+1)Ave#(m)+2

Czy jest więc prawdą, że

(m+1)Ave#(m+1)>=(m+1)lg(m+1)

albo

(m+1)Ave#(m+1)=(m+1)Ave#(m)+2>=(m+1)lgm+2>=(m+1)lg(m+1)

Po przekształceniu ostatniej nierówności dostajemy

2>=lg[(m+1)/(m)]^(m+1)=lg(1+1/m)+lg(1+1/m)^m->lg1+lge=lge=w przyb.1,44

co jest prawdą dla każdego m > 1 . Kończy to dowód naszego stwierdzenia.
Wykazaliśmy, że dla losowo wybranego liścia w drzewie decyzyjnym o m liściach należy się spodziewać, iż długość ścieżki prowadzącej od korzenia do tego liścia będzie nie mniejsza niż lgm. Liczba liści w drzewie decyzyjnym umożliwiającym rozwiązanie problemu sortowania n elementów jest nie mniejsza niż n!, które jest równe liczbie wszystkich możliwych uporządkowań n-elementowej tablicy. Skoro m>n!, to i lgm>=lg(n!). Ten smutny wynik oznacza, że przypadek średni, podobnie jak najgorszy, wymaga lg(n!) porównań (długość ścieżki = liczba porównań), a jak już wcześniej oszacowaliśmy, lg(n!)=O(nlgn). Niczego lepszego nie można się spodziewać również w średnim przypadku.

535

A.3. Średnia złożoność algorytmu guicksort

Oznaczmy przez C(ni) liczbę porównań potrzebnych do posortowania n-elementowej tablicy za pomocą algorytmu ąuicksort. Ponieważ tablic rozmiaru 1 ani 0 się nie dzieli, więc C(0) = C(1) = 0. Przy założeniu losowego uporządkowania tablicy każdy jej element może zostać wybrany za rozdzielający z jednakowym prawdopodobieństwem. Skoro C(i- 1) i C(n-i) oznaczają liczby porównań potrzebnych do posortowania obydwu podtablic (Gwoli ścisłości trzeba by jeszcze udowodnić, że podtablice
otrzymane w wyniku podziału losowej tablicy są również losowe (przyp. tłum.).) dla n >= 2 mamy

C(n)=n-1+1/n[Sigma#i=1;^n(C(i-1)+C(n-i))] dla n>=2

porównań, gdzie n - 1 to liczba porównań przy podziale tablicy rozmiaru n. Wzór ten można nieco uprościć:

C(n)=n-1+1/n[Sigma#i=1;^n(C(i-1))+Sigma#i=1;^n(C(n-i))]=n-1+1/n[Sigma#i=1;^n(C(i-1))+Sigma#j=1;^n(C(j-1))]=
n-1+2/n[Sigma#[(i=1);^(n-1)](C(i))]

czyli
nC(n)=n(n-1)+2[Sigma#[(i=1);^(n-1)](C(i))]

Aby rozwiązać to równanie, najpierw trzeba pozbyć się operatora sumowania. W tym celu ostatnie równanie odejmujemy od otrzymanego z niego równania

(n+1)C(n+1)=(n+1)n+2[Sigma#i=1;^n(C(i))]

w wyniku czego dostajemy

(n+1)C(n+1)-nC(n)=(n+1)n-n(n-1)+2[Sigma#i=1;^n(C(i))+Sigma#i=1;^n-1(C(i))]

skąd

[C(n+1)]/(n+2)=C(n)/(n+1)+2n/[(n+1)(n+2)=C(n)/(n+1)+4/(n+2)-2/(n+1)

536

To ostatnie równanie można rozwinąć, otrzymując

C(2)/3=C(1)/2+4/3-2/2=4/3-2/2

C(3)/4=C(2)/3+4/4-2/3

C(4)/5=C(3)/4+4/5-2/4
.
.
.
C(n)/(n+1)=C(n-1)/(n)+4/(n+1)-2/n

C(n+1)/(n+2)=C(n)/(n+1)+4/(n+2)-2/(n+1)

stąd

C(n+1)/(n+2)=(4/3-2/2)+(4/4-2/3)+(4/5-2/4)+...+(4/(n+1)-2/n)+(4/(n+2)-2/(n+1))=2/2+2/3+2/4+2/5+...+2/n+2/(n+1)+4/(n+2)=
-4+2H#(n+2)+2/(n+2)

H#(n+2) jest liczbą harmoniczną. Korzystając z oszacowania tej liczby (por. dodatek A.1), dostajemy

C(n)=(n+1)[-4+2H#(n+1)+2/(n+1)]=(n+1)[-4+2O(lnn)+2?(n+1)=O(nlgn)

A.4. Średnia długość ścieżki w losowym drzewie binarnym

W rozdziale 8 używaliśmy oszacowania średniej długości ścieżki w losowo utworzonym drzewie poszukiwań binarnych. Przy założeniu, że

P#i(i)=[(i-1)(P#(i-1)+1)+(n-i)(P#(n-i)+1)] / (n)
537

oszacowanie to dane jest wzorem rekurencyjnym

P#1=0

P#n=1/(n)[Sigma#i=1;^n(P#n(i))]=1/(n^2){Sigma#i=1;^n[(i-1)(P#(i-1)+1)+(N-1)((P#(i-i)+1)]}

(1) P#n=2/(n){Sigma#i=1;^n-1[i(P#(i)+1)]}

Mamy stąd również

(2) P#(n-1)=2/(n-1)^2{Sigma#i=1;^n-1[i(P#(i-1)+1)]}

Po pomnożeniu tego równania przez (n-1)^2/(n^2) i odjęciu wyniku od (1) mamy

P#n=P#(n-1)-[n^(2)-1]/(n^2)+[2(n-1)]/(n^2)=(n-1)/(n^2)[P#(n-1);(n+1)+2]

Stosując ten wzór wielokrotnie do jego prawej strony, otrzymujemy

P#n=(n-1)/(n^2)[(n+1)*(n-2)/(n-1)^2[n*(n-3)/(n-2)^2[(n-1)*(n-4)/(n-3)^2[...1/(2^2*{P#(1)3+2)]+2]+2]+2]]

P#n=2[(n-1)/(n)+((n+1)(n-2))/((n-1)n^2)+((n+1)(n-3))/(n(n-1)(n-2))+((n+1)(n-4))/((n(n-2)(n-3))+...+1/(2*3}]

P#n=[(n+1)/(n)*Sigma#i=1;n-1[(n-i)/((n-i+1)(n-i+2))]=2[(n+1)/(n)]*Sigma#i=1;^n-1[(2)/(n-i+2)-(1)/(n-i+1)]

P#n=2[(n+1)/(n)]*2/(n+1)+2[(n+1)/(n)][Sigma#i=1;^n[(1)/(n)-2]]=2[(n+1)/(n)]H#n-4

Zatem P#n wynosi O(ln n)