Diviser pour régner. Comportement asymptotique.

Diviser pour régner
Comportement asymptotique

Page de Philippe Dumas
Diviser pour régner | Maple | Livres
Publications | Adresse | English version

Introduction
Une idée fondamentale
Complexité et récurrences
Suites 2-rationnelles
Comportement asymptotique
Références

L'asymptotique des suites diviser pour régner est fondamentale en algorithmique puisque l'efficacité d'un algorithme est donnée par son comportement sur des données de grande taille. On peut distinguer deux approches : une approche élémentaire et une approche sophistiquée.

Approche élémentaire. Commençons par l'approche élémentaire. C'est celle qui est employée dans la quasi-totalité des ouvrages sur le sujet, [6, p. 117], [9, chap. 4], [19, p. 546]. Les résultats indiqués sont souvent démontrés de façon expéditive; à l'occasion il sont faux par manque de précison dans les hypothèses. Il est impossible de traiter tous les cas de figure et il semble plus intéressant d'énoncer des résultats clairs, valables dans une classe bien déterminées de récurrences. Ce cadre fournira une heuristique pour les exemples rencontrés dans la pratique et ceux-ci seront traités par une méthode ad hoc si le besoin s'en fait sentir.

Les suites (T_n) qui satisfont la récurrence

$\begin{displaymath} T_n=aT_{\lfloor n/2\rfloor}+f_n,\end{displaymath}$

où $a\geq1$ et la suite (f_n) est donnée, constituent une classe simple. Leur comportement asymptotique est fourni par le résultat suivant.

i.: Si $f_n=O(n^{\log_2{a}+\varepsilon})$ alors $T_n=O(n^{\log_2{a}+\varepsilon})$ pour tout $\varepsilon\gt$ .
ii.: Si les deux suites (f_n) et (T_n) sont à valeurs strictement positives et $f_n=\Theta(n^{\log_2{a}})$ alors $T_n=\Theta(n^{\log_2{a}}\log_2{n})$ .
iii.: Si $f_n=O(n^{\log_2{a}-\varepsilon})$ alors $T_n=O(n^{\log_2{a}})$ pour tout $\varepsilon\gt$ .

Rappelons qu'en informatique la notation $\Theta$ est employée pour exprimer la similitude, plutôt notée $\asymp$ en mathématiques; la relation $u_n=\Theta(v_n)$ abrège la conjonction des deux relations u_n=O(v_n) et v_n=O(u_n).

Une heuristique fréquemment utilisée pour déterminer le comportement d'une suite diviser pour régner consiste à l'évaluer sur les puissances de 2. Dans l'optique des suites 2-rationnelles cette démarche est naturelle : une telle suite traduisant une série rationnelle au sens de la théorie des langages, une sous-suite associée aux entiers dont l'écriture binaire est de la forme (uv^k)₂, où u et v sont deux motifs fixés, a une série génératrice rationnelle au sens ordinaire; cette sous-suite vérifie donc une relation de récurrence linéaire à coefficients constants de type classique. La suite étant évaluée sur les puissances de 2 on peut ensuite, moyennant des hypothèses de monotonie et de régularité [19, p. 565], étendre la comparaison à tous les entiers.

Le résultat simple que nous avons indiqué fournit la complexité de plusieurs algorithmes diviser pour régner. La multiplication d'entiers par la méthode de Karatsuba, la multiplication de polynômes, la multiplication de matrices par la méthode de Strassen ont des coûts majorés par des suites qui vérifient

$\begin{displaymath} u_n=3u_{\lfloor n/2\rfloor}+cn,\qquad v_n=7v_{\lfloor n/2\rfloor}+cn^2,\end{displaymath}$

respectivement pour les deux premières et pour la dernière. Elles ont donc des coûts respectivement en $O(n^{\log_23})$ et $O(n^{\log_27})$ , et donc en O(n^1,58) et O(n^2,81). On remarque que ceci est asymptotiquement meilleur que les coûts des algorithmes naïfs qui sont respectivement en O(n²) et O(n³).

Pour le tri-fusion les coûts dans le cas moyen et dans le cas le pire satisfont tous les deux une récurrence de la forme

$\begin{displaymath} T_n=T_{\lfloor n/2\rfloor}+T_{\lceil n/2\rceil}+O(n).\end{displaymath}$

Le deuxième point ne s'applique pas tel que, mais une simple variante montre que le coût est dans les deux cas un $O(n\log_2n)$ . Dans la recherche de l'enveloppe convexe par le méthode diviser pour régner la partie la plus coûteuse est le tri des points suivant leur abscisse et on a donc encore une complexité en $O(n\log_2n)$ . On peut renforcer ces résultats par une évaluation expérimentale dans le cas moyen.

On pourrait donner bien d'autres illustrations; nous renvoyons le lecteur à [7, pp. 23-24], [9, §28.5],[9, § 29.3.2], [9, §35.4], [14, p. 172], [20, §5.1.7], [24, p. 190], [27, p. 27], [32, pp. 153, 164]), [33, § 10.2], [34, chap. 28]. On consultera aussi [18], [26, §4.6.3], [28] ainsi que [13].

Approche sophistiquée. Abordons maintenant l'approche sophistiquée. Les suites diviser pour régner que l'on rencontre en analyse d'algoritmes ont un comportement polynomial c'est-à-dire en $O(n^{\alpha})$ . C'est par exemple le cas de toutes les suites 2-rationnelles; en effet une telle suite (u_n) s'exprime par

$\begin{displaymath} u_n=\lambda A_{n_\ell}\dotsb A_{n_0}\gamma\qquad\text{si $n=(n_{\ell}\ldots n_0)_2$}\,;\end{displaymath}$

on en tire tout de suite

$\begin{displaymath} \vert u_n\vert\leq \Vert \lambda\Vert \Vert A_{n_\ell}\Vert\... ...\gamma\Vert\leq C\max(\Vert A_0\Vert,\Vert A_1\Vert)^{\ell+1}, \end{displaymath}$

en utilisant une norme sur l'espace de dimension N, et ceci fournit la majoration annoncée car la longueur de l'écriture binaire de n est en $\log_2{n}$ .

Une telle majoration permet de considérer la série de Dirichlet associée à la suite,

$\begin{displaymath} u(s)=\sum_{n\geq1}\frac{u_n}{n^s}.\end{displaymath}$

Elle est définie dans un demi-plan droit du plan complexe et très souvent elle se prolonge en une fonction méromorphe dans tout le plan. C'est en particulier le cas pour les suites 2-rationnelles car la série de Dirichlet vérifie alors une équation fonctionnelle infinie qui exprime u(s) en fonction de u(s+1), u(s+2), etc. D'autre part la formule de Perron [5, p. 245], [36, p. 147],

$\begin{displaymath} \sum_{n<N}u_n+\frac{1}{2}u_N=\frac{1}{2i\pi} \int_{c-i\infty}^{c+i\infty}u(s)N^s\frac{ds}{s},\end{displaymath}$

dans laquelle l'intégration se fait sur une verticale située à droite de l'abscisse de convergence absolue, permet d'exprimer les sommes partielles de la suite. Si la fonction u(s) a un bon comportement vers $i\infty$ on peut pousser la droite d'intégration vers la gauche, en sautant par dessus les pôles, et en collectant les résidus on obtient un développement asymptotique disons en moyenne de Cesàro, qui à l'occasion peut être une expression exacte. Par exemple [17], la suite (S_n) qui donne le nombre de 1 dans les écritures binaires des entiers entre 1 et n vaut

$\begin{displaymath} S_n=\frac{1}{2}n\log_2{n}+nF(\log_2n),\end{displaymath}$

où F(u) est la série de Fourier

$\begin{displaymath} F(u)=\frac{\log_2\pi}{2}-\frac{1}{2\log 2}-\frac{3}{4}- \fra... ...sum_{k\neq0}\frac{\zeta(\chi_k)}{\chi_k(\chi_k+1)} e^{2ik\pi u}\end{displaymath}$

et $\zeta(s)$ est la fonction dzêta de Riemann, $\chi_k=2ik\pi/\log 2$ ; de même le nombre $\Phi_n$ de coefficients binomiaux impairs dans les n premières lignes du triangle de Pascal vaut

$\begin{displaymath} \Phi_n=n^{\log_23}\,G(\log_2n),\end{displaymath}$

où G(u) est périodique de période 1 définie par sa série de Fourier.

Le point remarquable de ces résultats est la mise en évidence de fluctuations périodiques en échelle logarithmique. On le constate dans le dessin ci-dessous où l'on a représenté la suite des points $(\log_2{n},\Phi_n/n^{\log_23})$ l'entier n allant de 1 à 1024. Sur ce domaine on peut consulter [16], [15], [2], [3].

La stratégie diviser pour régner apparaît ainsi comme une méthode d'obtention d'algorithmes efficaces. De plus elle conduit à une vaste classe de récurrences. Leur étude algébrique montre des liens avec la théorie des automates et plus généralement les séries rationnelles de la théorie des langages formels. D'autre part leur asymptotique fine repose sur des méthodes de la théorie analytique des nombres, qui permettent d'expliquer les fluctuations que l'on observe expérimentalement.

Page précédente : Suites 2-rationnelles
Page suivante : Références

Page précédente :	Suites 2-rationnelles
Page suivante :	Références