Twierdzenie główne nie dotyczy?

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

$$T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ chcemy zastosować twierdzenie Master i zauważyć, że

$$n^{\log_2(2)} = n.$$

Teraz sprawdzamy dwa pierwsze przypadki dla $\varepsilon > 0$ , czyli czy

• $n\log n \in O(n^{1-\varepsilon})$ lub
• $n\log n \in \Theta(n)$ .

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

• $n\log n \in \Omega(n^{1+\varepsilon})$ .

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?

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) = n \log n$ rośnie szybciej niż $n$ ale wolniej niż $n^{1+\varepsilon}$ dla dowolnego $\varepsilon > 0$ .

Twierdzenie to można jednak uogólnić w celu uwzględnienia tego nawrotu. Rozważać

Przypadek 2A: Rozważmy $f(n) = \Theta (n^{\log_b a }\log_b^k n)$ dla niektórych $k\geq 0$ .

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 $\Theta (\log_b n)$ razy. Szkic bardziej formalnego dowodu można znaleźć poniżej. Ostateczny wynik jest taki

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n)$$ .

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) = \Theta(n \cdot \log^2 n).$$

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

$$\lim_{x\to c} \frac{f(x)}{g(x)} = \lim_{x\to c} \frac{f^\prime(x)}{g^\prime(x)}$$

żadnych funkcji $f(x)$ i $g(x)$ różniczkowej w pobliżu $c$ . Stosując to $f(n) = n \log n$ i $g(n) = n^{1+\varepsilon}$ można wykazać, że $\log n \not\in \Theta (n^{1+\varepsilon}).$

---

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) = \displaystyle \sum_{j=0}^{\log_b {n-1}} a^j h(n/b^j)$$

gdzie $h(n) = n^{\log_b a} \log_b^k n.$Następnie $g(n) = n^{\log_b a} \log_b^{k +1} n.$

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

$$g(n) = \displaystyle n^{\log_b a} \log_b^k n \; \sum_{j=0}^{\log_b{n-1}} \left(\frac{a}{b^{\log_b a}}\right)^j = n^{\log_b a} \log_b^{k +1} n.$$

CO BYŁO DO OKAZANIA

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

$$T(n) = a T(n/b) + f(n),\quad T(1) = \Theta(1)$$

można to przepisać jako

$$T(n) = \Theta(n^{\log_b a}) + \displaystyle \sum_{j=0}^{\log_b n - 1} a^j f(n/b^j).$$

$f(n)$$\Theta(n^{\log_b a} \log_b^k n)$$\Theta$

$$T(n) = \Theta (n^{\log_b a }\log_b^{k+1} n).$$

$n$$b$

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) \sim g(n)$