Complexité en temps d'une fonction récursive

[vinze80]

Bonjour,

Je cherche à identifier la complexité en temps d'une fonction récursive. La fonction s'appelle elle même avec une valeur de n//3 à chaque nouvel appel (ne garde que la partie entière de la division de n par 3).

La relation de récurrence est du type :
Mais à partir de cette relation, je n'arrive pas à avancer.
Je sais que le résultat final est du type

Mais j'aimerais comprendre le cheminement pour arriver à ce résultat.

Merci.
-----

[pm42]

Donc tu divises par n par 3 jusqu'à ce que tu arrives à 0 (ou 1).
Donc tu divises n par 3^x et tu te demandes quelle doit être la valeur de x pour que n/3^x <= 1 soit n=3^x.

Tu peux aussi montrer que la complexité est en log3(n) par récursivité.

[vinze80]

Merci pour la réponse.

Pourquoi avoir choisi inférieur ou égal à 1 dans :

Après je vois bien apparaitre le

Comment dois-je faire pour le faire par récursivité ?

Merci.

[pm42]

Pourquoi avoir choisi inférieur ou égal à 1 dans :

Parce qu'en général, les fonctions récursives s'arrêtent pour n=1 ou n=0.

Comment dois-je faire pour le faire par récursivité ?

En calculant la complexité pour n=1 puis pour n=3, n=9, etc.

[A voir en vidéo sur Futura]

[vinze80]

En calculant la complexité pour n=1 puis pour n=3, n=9, etc.

Je m'aperçois que :


J'ai donc quelque chose de la forme
Mais comment écrire ça correctement mathématiquement ?

Merci