Forum de mathématiques - Bibm@th.net

Pfiou

Invité

Récurrence et algorithme

Bonjour, j'étudie un algorithme récursif (Tri fusion), où je dois calculer la complexité de celui-ci.

J'ai tout d'abord calculer le nombre d'itérations de cet algorithme, je trouve ceci :

[tex]\left\lbrace\begin{matrix} & T(1) = 1 \\ & T(n) = 2n+1 + 2 * T(\frac{n}{2}) \end{matrix}\right.[/tex]

Et à partir de là, je dois prouver la complexité par récurrence, et donc exprimer T(n) en fonction de n. Cependant, j'avoue ne pas trop savoir comment faire, le T(n/2) me gêne ...

Paco del Rey

Invité

Re : Récurrence et algorithme

Bonsoir Pfiou.

À ta place je poserais $u_n = T\left(2^n\right)$.

Paco.

Pfiou

Invité

Re : Récurrence et algorithme

Merci pour ta réponse, mais pourquoi cette valeur ? Je sais que c'est pour simplifier les choses, mais je n'arrive pas à trouver la relation entre [tex]2*T(\frac{n}{2}) [/tex] et [tex] T(2^{n})[/tex]  qui t'as permis de trouver cela

Paco del Rey

Invité

Re : Récurrence et algorithme

Tu as

\[ T(2^n) = 2\times2^n+1+2\times T(2^{n-1} \]
donc
\[ u_n = 2^{n+1} + 1 + 2u_{n-1}. \]
avec \( u_0 = T(2^0) = 1 \).
Reste à résoudre cette récurrence.

Paco.

Pfiou

Invité

Re : Récurrence et algorithme

Merci beaucoup. Je suis en train d'essayer de la résoudre afin d'obtenir Un en fonction de n.

Pfiou

Invité

Re : Récurrence et algorithme

En fait, je crois n'avoir pas bien compris la question. Il me semble difficile d'obtenir la forme explicite de cette récurrence, non ?

La question est la suivante :

6.1 Complexité

Quelle est la complexité de cet algorithme (donner une preuve par récurrence) ?

J'ai donc calculé comme dit plus haut les différentes itérations, pour en trouver la suite T(n). De ce que j'avais compris, il faut que je trouve une équation qui exprime T(n) en fonction de n pour en déduire la complexité. Cependant, cela me semble difficile ou alors je m'y suis mal pris.

Paco del Rey

Invité

Re : Récurrence et algorithme

Il me semble difficile d'obtenir la forme explicite de cette récurrence, non ?

Celle que je propose ? Non.

Paco.

Pfiou

Invité

Re : Récurrence et algorithme

D'accord, quelle est la méthode pour la trouver ?

Paco del Rey

Invité

Re : Récurrence et algorithme

C'est standard :

1) Tu résous l'équation sans second membre : $u_n = 2u_{n-1}$.
2) Tu trouves une solution particulière de $u_n = 2^{n+1}  + 2u_{n-1}$.
3) Tu trouves une solution particulière de $u_n = 1 + 2u_{n-1}$.
4) Tu fais la somme des trois et tu détermines le coefficient inconnu grâce à la condition initiale $u_0=1$.

Paco.