Preuve rigoureuse de la validité de l'hypothèse

Le théorème maître est un bel outil pour résoudre certains types de récurrences . Cependant, nous masquons souvent une partie intégrante lors de son application. Par exemple, lors de l'analyse de Mergesort, nous sommes heureusement passés de

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considérant seulement $n=2^k$ . Nous nous assurons que cette étape est valide - c'est-à-dire $T \in \Theta(T')$ - parce que $T$ se comporte "bien". En général, nous supposons $n=b^k$ pour $b$ le dénominateur commun.

Il est facile de construire des récurrences qui ne permettent pas cette simplification en utilisant vicious $f$ . Par exemple, au-dessus de la récurrence de $T\,$ / $\,T'$ avec

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

produira $\Theta(n)$ en utilisant le théorème maître de la manière habituelle, mais il y a clairement une sous-séquence qui grandit comme $\Theta(n \log n)$ . Voir ici pour un autre exemple plus artificiel.

Comment rendre cela "bien" rigoureux? Je suis tout à fait certain que la monotonie est suffisante, mais même la simple récurrence de Mergesort n'est pas monotone; il y a une composante périodique (qui est dominée asymptotiquement). Suffit-il d'étudier $f$ , et quelles sont les conditions nécessaires et suffisantes sur $f$ pour garantir le fonctionnement du théorème maître?

asymptotics proof-techniques recurrence-relation master-theorem Raphael
la source

Un autre point de vue sur les mêmes résultats est le théorème d'Akra-Bazzi "Sur la solution des équations de récurrence linéaire", Computational Optimization and Applications, 10 (2), 195-210 (1998), ou Drmota et Szpankowski "A Master Theorem for Discrete Divide et conquérir les récurrences ", SODA'11 < dl.acm.org/citation.cfm?id=2133036.2133064 >.

vonbrand

Voici un lien vers le document ci-dessus, qui n'est pas derrière un mur payant.

Paresh

IIRC ceci est discuté dans CLRS chapitre 4.

Kaveh

@Kaveh Merci pour le pointeur. Pour la plupart, ils appellent cela une «négligence tolérable»; c'est bien dans leur contexte, car ils supposent que vous ne dérivez qu'une hypothèse, qui sera ensuite confirmée par induction. Ils mentionnent les dangers (4.6). En 4.6.2, ils donnent une preuve, mais elle est de haut niveau et ils ne disent pas explicitement quelles restrictions sur

doivent être en place. Il semble donc que ce soit quelque chose comme "

tel que les calculs passent", ce qui, je pense, nécessite principalement que

ait une "belle" classe

T

$T$

T

$T$

f

$f$

Θ

$\Theta$

Raphael

En général, lorsque vous n'avez pas de tailles similaires, vous pouvez utiliser la méthode Akra – Bazzi qui est la généralisation du théorème maître, bien sûr, comment changer une fonction spécifique en quelque chose qui fonctionne dans ce théorème a besoin d'une petite astuce, et pour quelque chose comme le tri par fusion, c'est ce que les gens utilisent normalement pour prouver la complexité du temps.

Tout au long de cette réponse, nous supposons que et sont non négatifs. Notre preuve fonctionne chaque fois que pour un monotone . Cela inclut votre exemple Mergesort, dans lequel , et toute fonction qui a un taux de croissance polynomial (ou même ). $f$ $T$ $f = \Theta(g)$ $g$ $f=\Theta(n)$ $\Theta(n^a \log^b n)$

Considérons d'abord le cas où est monotone non décroissant (nous assouplirons cette hypothèse plus tard). Nous nous concentrons sur votre récurrence d'échantillon Cette récurrence nécessite deux cas de base, et . Nous faisons l'hypothèse que $f$

T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) .

$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n).$

T (0)

$T(0)$

T (1)

$T(1)$

, que nous relaxons également plus tard.

T (0) \leq T (1)

$T(0) \leq T(1)$

Je prétends que est monotone non décroissant. Nous prouvons par induction complète que . Ceci est donné pour , donc soit . Nous avons $T(n)$ $T(n+1) \geq T(n)$ $n = 0$ $n \geq 1$ Cela implique que Donc, si

\begin{aligned} T (n + 1) & = T (⌊ (n + 1) / 2 ⌋) + T (⌈ (n + 1) / 2 ⌉) + f (n + 1) \\ \geq T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + f (n) = T (n) . \end{aligned}

$\begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*}$

T (2^{⌊ \log_{2} n ⌋}) \leq T (n) \leq T (2^{⌈ \log_{2} n ⌋}) .

$T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}).$

, nous avons terminé. C'est toujours le cas si la solution pour des puissances de deux est de la forme

T (2^{m}) = Θ (T (2^{m + 1}))

$T(2^m) = \Theta(T(2^{m+1}))$

T (n) = Θ (n^{a} \log^{b} n)

$T(n) = \Theta(n^a \log^b n)$

Relâchons maintenant l'hypothèse que . Considérons une nouvelle récurrence définie exactement de la même manière, seulement . On peut prouver par récurrence que $T(0) \leq T(1)$ $T'$ $T'(0) = T'(1) = \min(T(0),T(1))$ $T'(n) \leq T(n)$ . De même, nous pouvons définir une nouvelle récurrence satisfaisant $T''$ , puis . En invoquant le théorème maître, nous voyons que et $T''(0) = T''(1) = \max(T(0),T(1))$ $T(n) \leq T''(n)$ $T'=\Theta(h)$ pour lamêmefonction , et donc également. $T''=\Theta(h)$ $h$ $T = \Theta(h)$

Maintenant relâchons l'hypothèse que est monotone. Supposons que $f$ pour une fonction monotone . Ainsi pour certains et assez grand. Nous supposons pour simplifier que ; le cas général peut être traité comme au paragraphe précédent. On définit à nouveau deux récurrences $f = \Theta(g)$ $g$ $cg(n) \leq f(n) \leq Cg(n)$ $c,C>0$ $n$ $n=0$ en remplaçant par (respectivement). Encore une fois, le théorème maître donnera le même résultat (jusqu'à des multiples constants), qui est également identique (jusqu'à des multiples constants) à ce que nous obtiendrions en résolvant la récurrence d'origine uniquement sur des puissances de deux. $T',T''$ $f$ $cg,Cg$

Yuval Filmus
la source

J'ai enfin pu lire cela de plus près. Bien, merci! Je pensais que je noterais cela pour les futurs lecteurs (parce que je suis tombé dessus):

n'est pas une restriction car il n'est faux que pour le super polynôme

et le Le théorème maître ne s'applique pas à cela.

T (2^{m}) \in Θ (T (2^{m + 1}))

$T(2^m) \in \Theta(T(2^{m+1}))$

T

$T$

Raphael

J'ai essayé d'écrire votre preuve plus en détail et je suis resté coincé à prouver votre dernière phrase, "qui est également identique (...) à ce que nous obtiendrions en résolvant la récurrence originale uniquement sur des puissances de deux". En particulier, nous devons montrer que nous nous retrouvons dans le même cas du théorème maître pour

. Ce n'est pas un problème pour les cas 1 et 2, mais je ne peux pas montrer l'existence de

pour le cas 3 (cf la version en CLRS, p94 en 3ème édition). Avez-vous pensé à cela ou avez-vous travaillé avec une version similaire à celle de Wikipedia ?

c g

$cg$

f

$f$

C g

$Cg$

c < 1

$c < 1$

Raphael

C'est une technicité. Si

alors le problème disparaît, voir par exemple users.encs.concordia.ca/~chvatal/notes/master.pdf . La fonction

satisfera automatiquement aux conditions. J'imagine que la même chose fonctionne pour

et ainsi de suite. Alternativement, il suffit d'énoncer cette condition directement sur

plutôt que sur

: il doit exister un

"régulier" satisfaisant

f = Θ (n^{α})

$f = \Theta(n^\alpha)$

g

$g$

f = Θ (n^{α} \log^{β} n)

$f = \Theta(n^\alpha \log^\beta n)$

g

$g$

f

$f$

g

$g$

f = Θ (g)

$f = \Theta(g)$

Yuval Filmus

g

$g$

f : n \mapsto 2^{n}

$f : n \mapsto 2^n$

g

$g$

c g

$cg$

C g

$Cg$

Je pense toujours que c'est une technicité. La condition qui vous inquiète est une condition technique. Pour la plupart des fonctions apparaissant en pratique, la condition est maintenue. Vous demandez la condition la plus générale dans laquelle le croquis de preuve ci-dessus passe. C'est une question intéressante à laquelle je suis trop paresseux pour répondre.

Yuval Filmus

Preuve rigoureuse de la validité de l'hypothèse

Réponses: