Pourquoi y a-t-il la condition de régularité dans le théorème maître?

J'ai lu Introduction aux algorithmes de Cormen et al. et je lis l'énoncé du théorème maître à partir de la page 73 . Dans le cas 3, il existe également une condition de régularité qui doit être satisfaite pour utiliser le théorème:

... 3. Si

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

pour une constante et si$\varepsilon > 0$

     [c'est la condition de régularité]$\qquad \displaystyle af(n/b) \leq cf(n)$

pour une constante et pour tout n suffisamment grand , alors ..$c < 1$$n$

Quelqu'un peut-il me dire pourquoi la condition de régularité est nécessaire? Comment le théorème échoue-t-il si la condition n'est pas satisfaite?

Pas une preuve rigoureuse, mais une explication "du haut de ma tête".

Imaginez la récurrence comme un arbre. Le troisième cas couvre le scénario où le nœud racine domine le temps d'exécution de manière asymptotique, c'est-à-dire que la plupart du travail est effectué dans un nœud maigre au sommet de l'arbre de récurrence. Le temps de course est alors Θ ( f ( n ) ) .$aT(n/b)+f(n)$$\Theta(f(n))$

Pour vous assurer que la racine fait plus de travail, vous avez besoin du

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

Cela signifie que (la quantité de travail effectuée à la racine) doit être au moins aussi grande que la somme du travail effectué aux niveaux inférieurs. (La récurrence est appelée une fois sur n / b de l'entrée.)$f(n)$$a$$n/b$

Par exemple, pour la récurrence le travail au niveau en dessous de la racine est un quart aussi grand et n'est effectué que deux fois ( n / 4 + n / 4 ) contre n de sorte que la racine domine .$T(n)=2T(n/4)+n$$(n/4+n/4)$$n$

Mais que se passe-t-il si la fonction ne remplit pas la condition de régularité? Par exemple, au lieu de n ? Ensuite, le travail effectué aux niveaux inférieurs peut être plus important que le travail effectué à la racine, vous n'êtes donc pas certain que la racine domine.$\cos(n)$$n$

Soit et b = 2 , de sorte que T ( 2 n ) = n ∑ k = 0 f ( 2 k ) . Pour que le cas 3 s'applique, nous avons besoin de f ( n ) = Ω ( n ϵ ) (pour certains ϵ > 0 ) et de la condition de régularité, f ( n / 2 ) ≤ ( 1 - δ ) $a = 1$$b = 2$

$$T(2^n) = \sum_{k=0}^n f(2^k).$$ $f(n) = \Omega(n^\epsilon)$$\epsilon > 0$ (pour certains δ > 0 ). Vous obtenez la condition de régularité de la preuve, c'est-à-dire que c'est un concept généré par la preuve. Bien que la condition de régularité ne soit pas nécessaire (considérez l'exemple donné sur Wikipedia, f ( n ) = n ( 2 - cos n ) ), vous ne pouvez pas la supprimer complètement, comme le montre l'exemple suivant. Considérons 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)$ Soitn=2m+1-1. Alors 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$ Il n'est donc pas vrai que T ( 2 n ) = Θ ( f ( 2 n ) ) . $$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))$

Il existe un théorème plus général, Akra-Bazzi, dans lequel la condition de régularité est remplacée par une quantité explicite qui entre dans le résultat.