Dlaczego w twierdzeniu głównym występuje warunek regularności?

Czytałem Wstęp do algorytmów Cormena i in. i czytam twierdzenie Twierdzenia Mistrza zaczynające się na stronie 73 . W przypadku 3 istnieje również warunek regularności, który należy spełnić, aby zastosować twierdzenie:

... 3. Jeśli

$\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon})$

dla niektórych stałych i if$\varepsilon > 0$

$\qquad \displaystyle af(n/b) \leq cf(n)$      [ jest to warunek prawidłowości ]

dla pewnej stałej i dla wszystkich wystarczająco dużych , to ...$c < 1$$n$

Czy ktoś może mi powiedzieć, dlaczego warunek prawidłowości jest potrzebny? Jak to twierdzenie zawodzi, jeśli warunek nie jest spełniony?

Nie jest to ścisły dowód, ale wyjaśnienie „z góry mojej głowy”.

Wyobraź sobie powtarzalność jako drzewo. Trzeci przypadek obejmuje scenariusz, w którym węzeł główny dominuje czas działania w sposób asymptotyczny, tj. Większość pracy jest wykonywana w wąskim węźle na szczycie drzewa cykliczności. Zatem czas działania wynosi Θ ( f ( n ) ) .$aT(n/b)+f(n)$$\Theta(f(n))$

Aby mieć pewność, że root rzeczywiście wykona więcej pracy, potrzebujesz

.$a f(n/b) \leq cf(n)$

Oznacza to, że (ilość pracy wykonanej w katalogu głównym) musi być co najmniej tak duża, jak suma pracy wykonanej na niższych poziomach. (Nawrót nazywa się razy n / b wejścia.)$f(n)$$a$$n/b$

Np. Dla nawrotu praca na poziomie poniżej korzenia jest o jedną czwartą większa i wykonywana tylko dwukrotnie ( n / 4 + n / 4 ) w stosunku do n, więc korzeń dominuje .$T(n)=2T(n/4)+n$$(n/4+n/4)$$n$

Ale co jeśli funkcja nie spełnia warunku regularności? Np. zamiast n ? Następnie praca wykonana na niższych poziomach może być większa niż praca wykonywana w katalogu głównym, więc nie masz pewności, że katalog główny dominuje.$\cos(n)$$n$

Niech = 1 i b = 2 , tak, że T ( 2 n ) = n Σ k = 0 f ( 2 K ) . Aby zastosować przypadek 3, potrzebujemy f ( n ) = Ω ( n ϵ ) (dla niektórych ϵ > 0 ) i warunek regularności, f ( n / 2 ) ≤ ( 1 - δ ) f$a = 1$$b = 2$

$$T(2^n) = \sum_{k=0}^n f(2^k).$$ $f(n) = \Omega(n^\epsilon)$$\epsilon > 0$ (dla niektórych δ > 0 ). Otrzymujesz warunek prawidłowości z dowodu, tzn. Jest to koncepcja wygenerowana z dowodu. Chociaż warunek prawidłowości nie jest konieczny (rozważ przykład podany na Wikipedii, f ( n ) = n ( 2 - cos n ) ), nie możesz go całkowicie upuścić, jak pokazano w poniższym przykładzie. Rozważmy f ( 2 n ) = 2 2 ⌊ log 2 n ⌋ > 2 2 log 2 n $f(n/2) \leq (1-\delta) f(n)$$\delta > 0$$f(n) = n(2-\cos n)$ Niechn=2m+1-1. Następnie T(2n)= m ∑ k = 0 2 k + 1 - 1 ∑ t = 2 k 2 2 k = m ∑ k = 0 2 2 k +k=Θ(2 2 m $$f(2^n) = 2^{2^{\lfloor \log_2 n \rfloor}} > 2^{2^{\log_2n-1}} = 2^{n/2}.$$ $n = 2^{m+1}-1$ $$T(2^n) = \sum_{k=0}^m \sum_{t=2^k}^{2^{k+1}-1} 2^{2^k} = \sum_{k=0}^m 2^{2^k+k} = \Theta(2^{2^m+m}), \quad f(2^n) = 2^{2^m}.$$ $T(2^n) = \Theta(f(2^n))$

Istnieje bardziej ogólne twierdzenie Akra-Bazzi, w którym warunek regularności jest zastępowany wyraźną wielkością, która pojawia się w wyniku.