Twierdzenie główne nie dotyczy?

11

Biorąc pod uwagę następujące równanie rekurencyjne

T(n)=2T(n2)+nlogn
chcemy zastosować twierdzenie Master i zauważyć, że

nlog2(2)=n.

Teraz sprawdzamy dwa pierwsze przypadki dla ε>0 , czyli czy

  • nlognO(n1ε) lub
  • nlognΘ(n) .

Oba przypadki nie są spełnione. Musimy więc sprawdzić trzeci przypadek, czyli czy

  • nlognΩ(n1+ε) .

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?

Joachim
źródło
4
Przypadek trzeci nie jest spełniony, ponieważ nie jest Ω ( n ϵ ) dla dowolnego ϵ > 0 . Użyj reguły l'Hôpital na dzienniku limitów nlognΩ(nϵ)ϵ>0lognnϵ
sdcvvc
1
Gdy pokażesz, że żaden przypadek nie ma zastosowania, jest to dowód, że nie możesz zastosować twierdzenia głównego, jak stwierdzono.
Raphael
Kto potrzebuje twierdzenia mistrza? Użyj drzew rekurencyjnych.
JeffE

Odpowiedzi:

7

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 znaczy f(n)=nlogn 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żmy f(n)=Θ(nlogbalogbkn) dla niektórych k0 .

Przypadek ten redukuje się do Przypadku 2, gdy k=0 . Jest intuicyjnie wiadomo, że wzdłuż każdej gałęzi drzewa nawrót f(x) jest dodana Θ(logbn) razy. Szkic bardziej formalnego dowodu można znaleźć poniżej. Ostateczny wynik jest taki

T(n)=Θ(nlogbalogbk+1n)
.

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

T(n)=Θ(nlog2n).

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

limxcf(x)g(x)=limxcf(x)g(x)

żadnych funkcji f(x) i g(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ę

g(n)=j=0logbn1ajh(n/bj)

gdzie h(n)=nlogbalogbkn.Następnie g(n)=nlogbalogbk+1n.

Dowód: podstawiając h(n) do wyrażenia g(n) można uzyskać

g(n)=nlogbalogbknj=0logbn1(ablogba)j=nlogbalogbk+1n.

CO BYŁO DO OKAZANIA

Jeśli n jest dokładną potęgą b danym nawrocie

T(n)=aT(n/b)+f(n),T(1)=Θ(1)

można to przepisać jako

T(n)=Θ(nlogba)+j=0logbn1ajf(n/bj).

f(n)Θ(nlogbalogbkn)Θ

T(n)=Θ(nlogbalogbk+1n).

nb

Dmitrij Chubarow
źródło
1

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 ;-)

T(n)g(n)

vonbrand
źródło