Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Entraide (supérieur)
- » Récurrence et algorithme
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- Paco del Rey
- 03-10-2021 22:34:55
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.
- Pfiou
- 03-10-2021 22:28:17
D'accord, quelle est la méthode pour la trouver ?
- Paco del Rey
- 03-10-2021 22:12:12
Il me semble difficile d'obtenir la forme explicite de cette récurrence, non ?
Celle que je propose ? Non.
Paco.
- Pfiou
- 03-10-2021 21:56:11
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.
- Pfiou
- 03-10-2021 21:39:58
Merci beaucoup. Je suis en train d'essayer de la résoudre afin d'obtenir Un en fonction de n.
- Paco del Rey
- 03-10-2021 18:07:18
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
- 03-10-2021 17:51:57
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
- 03-10-2021 17:38:36
Bonsoir Pfiou.
À ta place je poserais $u_n = T\left(2^n\right)$.
Paco.
- Pfiou
- 03-10-2021 17:24:26
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 ...