Théorème d'Akra-Bazzi

En informatique, le théorème d'Akra-Bazzi, appelé aussi la méthode d'Akra-Bazzi, sert à déterminer le comportement asymptotique des solutions de suites définies par récurrence qui apparaissent dans l'analyse asymptotique des coûts d'algorithme, notamment de la classe des algorithmes diviser pour régner. Le théorème est publié en 1998 et constitue une généralisation du Master theorem, puisque ce dernier ne s'applique qu'aux algorithmes du type « diviser pour régner » dont les sous-problèmes sont essentiellement de même taille.

Formulation mathématique

On considère l'équation de récurrence :

$T(x)=g(x)+\sum _{i=1}^k{a}_{i}T(b_{i}x+h_i(x))$ pour $x\ge x_0,$

où $T:{ℝ}^{+}\to {ℝ}^{+}$ est une fonction qui satisfait les conditions suivantes :

• La fonction est définie pour un nombre suffisant de valeurs initiales pour admettre une solution unique ;
• Les nombres $a_i$ et $b_i$ sont des constantes pour tous les indices $i$, et $a_i>0$ et $0<b_i<1$ ;
• Pour la dérivée $g^{\prime }(x)$ de $g(x)$, on a $|g^{\prime }(x)|=O\left(x^c\right)$, pour une constante $c$ ($O$ est le symbole de la notation de Landau) ;
• $|h_i(x)|=O\left(\frac{x}{{\log }^{2}x}\right)$ pour tout i ;
• $x_0$ est une constante.

Alors $T(x)$ admet l'estimation suivante de son comportement asymptotique ($\mathrm{\Theta }$ le symbole de la notation de Landau) :

$T(x)=\mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}\mathrm{d}u)\right)$

où $p\in {ℝ}^{+}$ est tel que $\sum _{i=1}^k{a}_i{b}_i^p=1$.

Les fonctions $h_i(x)$ représentent une petite perturbation de l’argument de T. Comme $\lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)$ et comme $\lfloor b_{i}x\rfloor -b_{i}x$ est toujours compris entre 0 et 1, on peut utiliser $h_i(x)$ pour ignorer les différences avec les parties fractionnaires de l’argument. Par exemple, les fonctions $T(n)=n+T\left(\frac{1}{2}n\right)$ et $T(n)=n+T\left(\lfloor \frac{1}{2}n\rfloor \right)$ ont, d'après le théorème d'Akra-Bazzi, le même comportement asymptotique.

Une variante de la condition sur la dérivée $g^{\prime }(x)$ de $g(x)$ est la condition de croissance polynomiale de $g(x)$ qui s'énonce comme suit : il existe des constantes positives $c_1$ et $c_2$ telles que pour $x\ge 1$ on ait

$c_{1}g(x)\le g(u)\le c_{2}g(x)$

pour tout réel $u$ dans la réunion des intervalles $[b_{i}x,x]$, pour $1\le i\le k$.

Exemples

Tri fusion

Pour le tri fusion le nombre T(n) de comparaisons qui est une bonne mesure de sa complexité en temps est donné par l'équation récursive :

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

avec comme cas initial $T(1)=0$. On peut appliquer le théorème d'Akra-Bazzi avec $g(u)=u+1$, $k=2$, $a_1=a_2=1$, $b_1=b_2=1/2$, et $p=1$, et on obtient le comportement asymptotique

$T(n)=\mathrm{\Theta }\left(n(1+\underset{1}{\overset{n}{\int }}\frac{u+1}{u^2}\mathrm{d}u)\right)=\mathrm{\Theta }\left(n(\ln n+2-\frac{1}{n})\right)=\mathrm{\Theta }(n\log n)$.

Diviser pour régner avec des sous-problèmes inégaux

On considère $T(n)$ définie par

$T(n)=n^2+\frac{7}{4}T\left(\lfloor \frac{1}{2}n\rfloor \right)+T\left(\lceil \frac{3}{4}n\rceil \right)$ pour $n>3$

et $T(n)=1$ pour $0\le n\le 3$. On prend $p=2$ de sorte que

$\frac{7}{4}{\left(\frac{1}{2}\right)}^p+{\left(\frac{3}{4}\right)}^p=1$.

La formule s'évalue alors comme suit :

$T(x)=\mathrm{\Theta }\left(x^p(1+\underset{1}{\overset{x}{\int }}\frac{g(u)}{u^{p+1}}\mathrm{d}u)\right)=\mathrm{\Theta }\left(x^2(1+\underset{1}{\overset{x}{\int }}\frac{u^2}{u^3}\mathrm{d}u)\right)=\mathrm{\Theta }(x^2(1+\ln x))=\mathrm{\Theta }(x^2\log x).$

Importance et autres exemples

Le théorème d'Akra-Bazzi couvre une très vaste classe d'équations récursives et généralise de manière substantielle les résultats connus précédemment pour déterminer le comportement asymptotique. Il est utilisé en informatique pour déterminer la complexité en temps d'algorithmes récursifs du type diviser pour régner. Les exemples suivants sont donnés dans les notes de Leighton et repris dans un cours de Chowdhury

Exemple 1

$T(x)=2T\left(\frac{x}{4}\right)+3T\left(\frac{x}{6}\right)+\mathrm{\Theta }(x\log x)$

On a $p=1$ et

$T(x)=\mathrm{\Theta }\left(x(1+\underset{1}{\overset{x}{\int }}\frac{u\log u}{u^2}\mathrm{d}u)\right)=\mathrm{\Theta }(x{\log }^{2}x)$

Exemple 2

$T(x)=2T\left(\frac{x}{2}\right)+\frac{8}{9}T\left(\frac{3}{4}x\right)+\mathrm{\Theta }\left(\frac{x^2}{\log x}\right)$

On a $p=2$ et

$T(x)=\mathrm{\Theta }\left(x^2(1+\underset{1}{\overset{x}{\int }}\frac{u^2/\log u}{u^3}\mathrm{d}u)\right)=\mathrm{\Theta }\left(\frac{x^2}{\log \log x}\right)$

Exemple 3

$T(x)=T\left(\frac{x}{2}\right)+\mathrm{\Theta }(\log x)$

On a $p=0$ et

$T(x)=\mathrm{\Theta }(1+\underset{1}{\overset{x}{\int }}\frac{\log u}{u}\mathrm{d}u)=\mathrm{\Theta }({\log }^{2}x)$

Exemple 4

$T(x)=\frac{1}{2}T\left(\frac{x}{2}\right)+\mathrm{\Theta }\left(\frac{1}{x}\right)$

On a $p=-1$ et

$T(x)=\mathrm{\Theta }\left(\frac{1}{x}(1+\underset{1}{\overset{x}{\int }}\frac{1}{u}\mathrm{d}u)\right)=\mathrm{\Theta }\left(\frac{\log x}{x}\right)$

Bibliographie

Article original

• Modèle:Article Modèle:Commentaire biblio SRL.

Exposés pédagogiques

• Modèle:Lien web.
• Modèle:Lien web.
• Modèle:Lien web.