Discussion :

[thecaptain]

Salut à tous

J'ai un petit souci mathématique afin de trouver l'ordre d'une récurrence :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
f²(n) = f²(n-1) + f²(n-2)

C'est une petite variante de la suite de fibonacci. Ma question est très simple : peut-on faire une substitution de fonction de la manière suivante => g(n) = f²(n) ? (la suite est simple) Sinon quelles sont les autres techniques que je peux utiliser ?

Merci d'avance !

@++

[pseudocode]

Trouver l'ordre de la récurrence ?

bah, heu... c'est 2

[thecaptain]

Hello

Oui, l'idée est de dire par exemple que f(n) = O(n²).
Le fait est que je connais les étapes à suivre et les méthodes à utiliser, c'est juste que je ne suis pas sur de ma substitution ci-dessus (à cause de la linéarité).

@++

[pseudocode]

T'es sur que tu ne confonds pas "ordre de la récurrence" avec autre chose ?

[thecaptain]

Re,

Ah okay, je comprends ta réponse '2' En fait, je cherche à exprimer la 'vitesse de croissance' de f(n), ce qui revient à chercher le O ('big oh') ou plus précisément le théta de f(n).

C'est mieux ?

@++

[pseudocode]

Re,

Ah okay, je comprends ta réponse '2' En fait, je cherche à exprimer la 'vitesse de croissance' de f(n), ce qui revient à chercher le O ('big oh') ou plus précisément le théta de f(n).

C'est mieux ?

@++

Ah... le comportement asymptotique ! Je me disais aussi que ca ne devait pas être aussi simple l'ordre de la récurrence.

Tu as une idée de la fonction asymptotique équivalente (theta(g)) et tu souhaites le démontrer ? Ou alors tu dois en trouver une ?

[Aleph69]

Bonjour,

tu peux poser g=f² sans aucun problème, c'est purement symbolique.

[Aleph69]

Concernant les autres techniques possibles, il y en a une couramment employée pour les problèmes de récurrence mais cela ne dit pas que ce soit utile dans ton cas. Elle consiste à considérer les sommes des termes de ta relation en s'arrangeant pour que beaucoup d'entre eux s'annulent. Cela demande tout de même un peu de réflexion pour savoir comment arranger les termes. A titre d'illustration, je te donne un exemple simple (mais pas très utile ici ) :

f²(n-0)-f²(n-1)=f²(n-2)
f²(n-1)-f²(n-2)=f²(n-3)
...
f²(3)-f²(2) = f²(1)
f²(2)-f²(1) = f²(0)

En sommant toutes les égalités, on obtient

f²(n)-f²(1) = f²(0)+f²(1)+...+f²(n-2)

A priori, la meilleure approche reste ton idée initiale de substitution pour te ramener à une suite plus classique de fonctions : comme ça, je dirais que ta suite converge deux fois plus vite que f(n)=f(n-1)+f(n-2).

[thecaptain]

Salut,

Ah... le comportement asymptotique ! Je me disais aussi que ca ne devait pas être aussi simple l'ordre de la récurrence.

Tu as une idée de la fonction asymptotique équivalente (theta(g)) et tu souhaites le démontrer ? Ou alors tu dois en trouver une ?

Ah merci pour la traduction Je dois trouver la fonction asymptotique.
Si je peux poser g(n) = f²(n) alors, c'est bon je sais continuer ! Je ne savais pas si cette substitution était 'valide' du point de vue de la linéarité.

comme ça, je dirais que ta suite converge deux fois plus vite que f(n)=f(n-1)+f(n-2)

A la base, j'avais trouvé theta(a^(n/2)) (pour fibonacci on trouve theta(a^n)). Il semblerait que ça aille dans ton sens

Merci pour vos infos !

@++