Calculs de complexité dans les ABR

  • Soit {C_n} le coût moyen (en termes de comparaisons) de la construction d’un ABR aléatoire de taille {n}. On a {C_0=C_1=0}.

On va insérer (à partir de l’arbre vide, par ajouts aux feuilles) les éléments de {\left\{1,\ldots,n\right\}}, dans un ordre aléatoire. Le premier entier inséré {k} va à la racine, donc le coût d’insertion est nul.

Il faut ensuite fabriquer les sous-arbres {A_g} (gauche) et {A_d} (droit) de {k}, de tailles respectives {k-1} et {n-k}. Le coût de construction de {A_g} est donc {C_{k-1}}, et celui de {A_d} est {C_{n-k}}.

On doit compter aussi les {n-1} comparaisons pour aiguiller les éléments de {\left\{1,2,\ldots,n\right\}\setminus\left\{k\right\}} soit vers {A_g} soit vers {A_d}. Il y a donc {C_{k-1}+C_{n-k}+n-1} comparaisons pour construire l’arbre après le choix de {k} à la racine.

Mais tous les choix de {k} sont équiprobables. Le coût moyen de fabrication d’un ABR de taille {n} est donc :

{\begin{array}{l}C_n=\frac1n\sum_{k=1}^{n}(C_{k-1}+C_{n-k}+n-1)\\[4pt]=n-1+\frac2n\sum_{k=1}^{n-1}C_k.\end{array}}
  • On trouve l’égalité {(E_n)} : {nC_n=(n-1)n+2\sum\limits_{k=1}^{n-1}C_k}.

On soustrait {(E_{n-1})} de {(E_n)} : {nC_n-(n-1)C_{n-1}=2(n-1)+2C_{n-1}}, donc {nC_n=2(n-1)+(n+1)C_{n-1}}.

Cette égalité peut s’écrire (valable pour {n\ge1}) :

{\frac{C_n}{n+1}=\frac{2(n-1)}{n(n+1)}+\frac{C_{n-1}}n=\frac4{n+1}-\frac2n+\frac{C_{n-1}}n.}

Par sommation :

{\begin{array}{l}\frac{C_n}{n+1}=\sum_{k=1}^{n}\left(\frac4{k+1}-\frac2k\right)\\[4pt]=2\sum_{k=1}^{n}\frac1k-\frac{4n}{n+1}\sim2\ln n.\end{array}}

Ainsi {C_n\sim2n\ln n} quand {n\to+\infty}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :