Biorąc pod uwagę następujące równanie rekurencyjne
chcemy zastosować twierdzenie Master i zauważyć, że
Teraz sprawdzamy dwa pierwsze przypadki dla , czyli czy
- lub
- .
Oba przypadki nie są spełnione. Musimy więc sprawdzić trzeci przypadek, czyli czy
- .
Myślę, że trzeci warunek również nie jest spełniony. Ale dlaczego? A jakie byłoby dobre wytłumaczenie, dlaczego w tym przypadku nie można zastosować twierdzenia mistrza?
Odpowiedzi:
Trzy przypadki twierdzenia mistrza, do których się odwołujesz, zostały udowodnione we wstępie do algorytmów Thomasa H. Cormena, Charlesa E. Leisersona, Ronalda L. Rivesta i Clifforda Stein'a (wydanie drugie, 2001).
Prawidłowo zaobserwowano, że omawiany nawrót przypada między przypadkiem 2 a przypadkiem 3. To znaczyfa( n ) = n logn rośnie szybciej niż n ale wolniej niż n1 + ε dla dowolnego ε > 0 .
Twierdzenie to można jednak uogólnić w celu uwzględnienia tego nawrotu. Rozważać
Przypadek 2A: Rozważmyfa( n ) = Θ ( nlogbzalogkbn ) dla niektórych k ≥ 0 .
Przypadek ten redukuje się do Przypadku 2, gdyk = 0 . Jest intuicyjnie wiadomo, że wzdłuż każdej gałęzi drzewa nawrót fa( x ) jest dodana Θ(logbn ) razy. Szkic bardziej formalnego dowodu można znaleźć poniżej. Ostateczny wynik jest taki
We wstępie do algorytmów to stwierdzenie pozostawia się jako ćwiczenie.
W końcu otrzymujemy to stwierdzenie w odniesieniu do wspomnianego ponownego wystąpienia
Więcej szczegółów na temat Twierdzenia Mistrza można znaleźć na doskonałej (imho) stronie Wikipedii .
Jak wskazuje @sdcvvc w komentarzach, aby udowodnić, że przypadek 3 nie ma tutaj zastosowania, można powołać się na zasadę L'Hospital, która mówi, że
żadnych funkcjifa( x ) i sol( x ) różniczkowej w pobliżu c . Stosując to f(n)=nlogn i g(n)=n1+ε można wykazać, że logn∉Θ(n1+ε).
Szkic dowodu twierdzenia głównego dla przypadku 2A.
Jest to reprodukcja części dowodu z Wprowadzenie do algorytmów z niezbędnymi modyfikacjami .
Najpierw udowodnimy następujący lemat.
Lemat A:
Rozważ funkcję
gdzieh(n)=nlogbalogkbn. Następnie
g(n)=nlogbalogk+1bn.
Dowód: podstawiająch(n) do wyrażenia g(n) można uzyskać
g(n)=nlogbalogkbn∑j=0logbn−1(ablogba)j=nlogbalogk+1bn.
CO BYŁO DO OKAZANIA
Jeślin jest dokładną potęgą b danym nawrocie
można to przepisać jako
źródło
Twierdzenie Akra-Bazzi jest ścisłym uogólnieniem twierdzenia głównego. Jako bonus jego dowodem jest zamieć całek, która sprawi, że głowa się zakręci ;-)
źródło