Résolution d'équations de récurrence contenant deux appels de récursivité

15

J'essaie de trouver un lié pour l'équation de récurrence suivante: $\Theta$

T (n) = 2 T (n / 2) + T (n / 3) + 2 n^{2} + 5 n + 42

$T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42$

Je pense que le théorème principal est inapproprié en raison de la quantité différente de sous-problèmes et de divisions. Les arbres de récursivité ne fonctionnent pas non plus car il n'y a pas de ou plutôt de . $T(1)$ $T(0)$

asymptotics recurrence-relation master-theorem Laura
la source

5

Si vous avez une récurrence de cette forme, il DOIT y avoir un cas de base, disons

T (n) \leq 42

$T(n) \leq 42$ pour tout

n < 100

$n < 100$ . Sinon, alors rien ne dit ce que la récurrence résoudra: peut-être

T (n) = 2^{m}

$T(n) = 2^m$ pour tout

n < 100

$n < 100$ , où

m

$m$ est la taille du problème d'origine! (imaginez une récursivité qui finit par comparer le nombre constant de tout ce que vous récursiez à tous les sous-ensembles des éléments originaux) En d'autres termes: aucun cas de base n'implique pas assez d'informations pour résoudre la récurrence.

Alex ten Brink

15

Oui, les arbres récursifs fonctionnent toujours! Peu importe que le cas de base se produise à $T(0)$ ou $T(1)$ ou $T(2)$ ou même $T(10^{100})$ . Peu importe également la valeur réelle du cas de base; quelle que soit cette valeur, c'est une constante.

Vu à travers de grosses lunettes Theta, la récidive est $T(n) = 2T(n/2)+T(n/3)+n^2$ .

La racine de l'arbre de récursivité a la valeur $n^2$ .
La racine a trois enfants, avec les valeurs $(n/2)^2$ , $(n/2)^2$ et $(n/3)^2$ . Ainsi, la valeur totale de tous les enfants est $(11/18) n^2$ .
Contrôle de santé mentale: la racine a neuf petits-enfants: quatre avec une valeur , quatre avec une valeur et un avec une valeur . La somme de ces valeurs est . $(n/4)^2$ $(n/6)^2$ $(n/9)^2$ $(11/18)^2 n^2$
Une preuve d'induction simple implique que pour tout entier , les nœuds au niveau ont une valeur totale . $\ell\ge 0$ $3^\ell$ $\ell$ $(11/18)^\ell n^2$
Les sommes de niveau forment une série géométrique descendante, donc seul le plus grand terme compte. $\ell=0$
Nous concluons que . $T(n) = \Theta(n^2)$

JeffE
la source

14

Vous pouvez utiliser la méthode Akra-Bazzi plus générale .

Dans votre cas, nous aurions besoin de trouver tel que $p$

\frac{1}{2^{p - 1}} + \frac{1}{3^{p}} = 1

$\frac{1}{2^{p-1}} + \frac{1}{3^p} = 1$

(ce qui donne ) $p \approx 1.364$

et nous avons ensuite

T (x) = Θ (x^{p} + x^{p} \int_{1}^{x} t^{1 - p} d t) = Θ (x^{2})

$T(x) = \Theta(x^p + x^p\int_{1}^{x} t^{1-p} \text{d}t) = \Theta(x^2)$

Notez que vous n'avez pas vraiment besoin de résoudre pour . Tout ce que vous devez savoir, c'est que . $p$ $1 \lt p \lt 2$

Une méthode plus simple serait de définir et d'essayer de prouver que est borné. $T(x) = x^2 g(x)$ $g(x)$

Aryabhata
la source

14

Soit un raccourci pour le côté droit de la récurrence. Nous trouvons une limite inférieure et supérieure pour en utilisant : $f(n) = 2T(n/2) + T(n/3) + 2n^2 + 5n + 42$ $f$ $T(n/3) \leq T(n/2)$

3 T (n / 3) + 2 n^{2} + 5 n + 42 \leq f (n) \leq 3 T (n / 2) + 2 n^{2} + 5 n + 42

$3 T(n/3) + 2n^2+ 5n + 42 \quad \le\quad f(n) \quad\leq \quad 3 T(n/2) + 2n^2+ 5n + 42 \quad$

Si nous utilisons le resp. Inférieur borne supérieure comme côté droit de la récurrence, nous obtenons dans les deux cas par le théorème maître. Ainsi, est borné d'en haut par et d'en bas par ou, de manière équivalente, . $T'(n) \in \Theta(n^2)$ $T(n)$ $O(n^2)$ $\Omega(n^2)$ $T(n) \in \Theta(n^2)$

Pour une preuve complète, vous devez prouver que est une fonction croissante. $T$

Raphael
la source

Continuons cette discussion par chat

Raphael

1

Cette astuce ne fonctionnera pas pour des récurrences similaires, comme , qui peuvent être résolues avec des arbres de récursivité. (Mais même les arbres de récursivité ne fonctionneront pas pour , ce qui peut être résolu avec Akra-Bazzi.)

T (n) = 2 T (n / 2) + 3 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 3T(n/3) + n^2$

T (n) = 2 T (n / 2) + 4 T (n / 3) + n^{2}

$T(n) = 2T(n/2) + 4T(n/3) + n^2$

JeffE

Résolution d'équations de récurrence contenant deux appels de récursivité

Réponses: