Clarification de la preuve impliquant la condition de régularité dans le théorème principal

Question

J'allais lire le texte Introduction aux algorithmes de Cormen et al.Où je suis tombé sur l'énoncé suivant dans la preuve du troisième cas du théorème de Maître.

(L'énoncé du théorème principal) Soit $a \geqslant 1$ et $b > 1$ être des constantes, soit $f(n)$ être une fonction, et soit $T (n)$ être défini sur les entiers non négatifs par la récurrence (la récursion divise un problème de taille $n$ dans $un$ problèmes de taille $n/b$ chacun et prend $f(n)$ pour diviser et combiner)

$T(n) = aT(n/b)+ f (n)$ ;

où nous interprétons $n/b$ signifier soit $\lceil b/n ceil$ ou $\létage b/n étage$.Alors $T(n)$ a les limites asymptotiques suivantes :

1. Si $f(n)=O (n^{\log_ba - \epsilon})$ pour une constante $\epsilon > 0$, alors $T(n)= hêta (n^{\log_ba})$.

2. Si $f(n)= hêta (n^{\log_ba})$, alors $T(n)= hêta (n^{\log_ba}\lg n)$

3. Si $f(n)=\Oméga (n^{\log_ba + \epsilon})$ pour une constante $\epsilon > 0$, et si $af(n/b) \leqslant cf(n)$ pour une constante $c < 1$ et tous n suffisamment grand, alors $T(n)= hêta (f(n))$.

Pour $n$ comme puissances exactes de $b$ nous restreignons le domaine de T(n) comme suit :

$$T(n)= hêta(1), n=1$$ $$T(n)=aT(n/b)+f(n) ,n=b^i$$

Maintenant dans la preuve du théorème de Master avec $n$ comme puissance exacte de $b$ l'expression pour $T(n)$ se réduit à :

$$T(n)= heta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Ensuite, les auteurs supposent ce qui suit :

$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Puis pour la preuve du 3ème cas du théorème de Master les auteurs prouvent le lemme suivant,

Lemme 1 :Si $a\cdot f(n/b)\leqslant c\cdot f(n)$ pour une constante $c<1$ et pour tous $n\geqslant b$ alors $g(n)= hêta(f(n))$

Ils disent ça:

sous leur hypothèse que $c<1$ et $n \geqslant b$,ils ont $a \cdot f(n/b)\leqslant c \cdot f(n) \implies f(n/b)\leqslant (c/a) \cdot f(n)$

alors itérer $j$ fois rendements, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$

Je n'arrivais pas à comprendre les mathématiques utilisées derrière itérer $j$ fois.

De plus, je ne parvenais pas à comprendre la logique derrière l'hypothèse de $n\geqslant b$ pour la situation qui $n$ devrait être suffisamment grand.(Comme le dit le troisième cas du théorème de Master.)

La preuve du lemme se poursuit ainsi :

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n )$$Donc, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$ $$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$ $$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ comme $c<1$ nous avons une série géométrique infinie$$= f(n) \left(\frac{1}{1-c} ight)$$ $$=O(f(n))$$ comme $c$ est une constante.(Noter que $T(n)=\Oméga(f(n))$ à partir du diagramme de récursivité.)

Ensuite, les auteurs démontrent le troisième cas du théorème de Masters pour $n$ comme puissance exacte de $b$:

Lemme 2:Laisser $a \geqslant 1$ et $b>1$, si $f(n)=\Oméga (n^{\log_ba + \epsilon})$ pour une constante $\epsilon > 0$, et si $af(n/b) \leqslant cf(n)$ pour une constante $c < 1$ et tous n suffisamment grand, alors $T(n)= hêta (f(n))$.

Donc $$T(n) = heta(n^{\log_ba}) + g(n) = heta(n^{\log_ba}) + heta(f(n)) = heta(f(n) )$$ comme $f(n)=\Oméga (n^{\log_ba + \epsilon})$

De plus, dans la preuve similaire pour le troisième cas du théorème général général (sans supposer $n$ comme puissances exactes de $b$) là encore, le livre suppose que $n\geqslant b+b/(b-1)$ aller avec la situation de suffisamment grande $n$.

Je ne comprends pas très bien ce que la valeur spécifique doit faire et pourquoi elle est considérée comme suffisamment grande $n$

(Je n'ai pas donné de détails sur la deuxième situation car je pense que ce sera quelque chose de similaire à la première situation mais quelle que soit la manière dont elle peut être trouvée ici)

Answer 1

Commençons par la question de l'itération.Supposons qu'une fonction $f$ satisfait$$ f(n/b) \leq (c/a)f(n).$$Ensuite, cela satisfait également$$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n).$$On peut prouver par récurrence que pour tout entier $t\geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n).$$

Quant à votre deuxième question, à propos de supposer que $n$ est assez grand :la preuve est tout simplement bâclée.Vous ne pouvez pas supposer que $f(n/b) \leq (c/a) f(n)$ vaut pour tous $n \geqb$.En effet, dans Introduction to Algorithms, troisième édition, ils ne font pas une telle hypothèse pour le cas où $n$ est un pouvoir de $b$.

Ils semblent faire une telle hypothèse dans le cas d'une situation générale. $n$, mais ce qu'ils disent en réalité, c'est que l'inégalité $f(\lceil n/b ceil) \leq (c/a) f(n)$ n'a de sens que pour $n \ge b + b/(b-1)$.En utilisant l'idée de la preuve du cas particulier où $n$ est un pouvoir de $b$, vous pouvez compléter la preuve du cas général.Je suggérerais cependant fortement d’ignorer ces détails techniques pour le moment.Le théorème principal est essentiellement un calcul, et vous pouvez faire confiance aux auteurs pour qu’il fonctionne.Rien d’intéressant n’est caché sous le tapis.