optimisation d'un algorithme récursif

[kizakoo]

Bonsoir, on nous demande dans un exo de donner la fonction permettant de calculer f (voir la photo ci-dessous) de complexité en temps minimale :



L'algorithme de calcul direct est un copier-coller de la formule mathématique mais sa complexité est conséquente
merci de votre aide
-----

[CM63]

Et quelle est ta question ? (à part j'aimerais qu'on fasse le travail à ma place).

[Jack]

Je ne vois pas l'intérêt de résoudre cet algorithme de manière récursive.

Il faudra gentiment signaler à ton prof qu'arithmétique ne prend pas de 'y'

[pm42]

Je ne vois pas l'intérêt de résoudre cet algorithme de manière récursive.

Je suis perplexe aussi. L'énoncé semble bien compliqué et sauf à avoir la suite, je dirais que la réponse serait d'utiliser la mémoïsation (https://fr.wikipedia.org/wiki/Mémoïsation) et donc d'échanger de la CPU contre de la mémoire.

Mais si c'est le cas, une grande partie de l'énoncé ne sert pas à grand chose.

[A voir en vidéo sur Futura]

[kizakoo]

Bonjour, merci de vos retours.
Je pense qu'il y'a une optimisation de l'algorithme parce que pour le calcul de f(n-3) on a besoin de f(n-5) et pour le calcul de f(n-2) on a besoin de f(n-5), f(n-5) sera alors calculée deux fois ...
Une optimisation consistera alors à calculer une valeur qu'une seule fois.

[pm42]

Une optimisation consistera alors à calculer une valeur qu'une seule fois.

Tu lis les réponses ?

[kizakoo]

Bonsoir, oui pm42 j'ai lu ta réponse et voici mes réponses à toutes les consignes.
Ci-dessous l'énoncé complet :

enoncé.jpg

Voici mes réponses :

rep1.jpg

rep2.jpg

pour le calcul de la complexité dans la question 3, on ne peut pas appliquer le master theorem et je n'ai pas eu d'idées de comment pouvons-nous calculer la complexité (la hauteur de l'arbre d'appels ? le nombre de nœuds de l'arbre d'appels ?)

Merci de vos retours sur ma rédaction et bonne soirée !

[kizakoo]

Pouvez-vous m'aider s'il vous plait ?
Mes réponses sont-elles correctes ?
Merci infiniment

[jacknicklaus]

réponse 1 : ok
réponse 2 : pourquoi ne développes tu pas f(4), f(5) etc..., bref tous les f(n) tels que n >= 4 ? Seuls les n < 4 sont évalués directement à 1. En faisant ca, tu comprendras bien mieux comment évolue le nombre de calculs f(x) à faire pour évaluer f(n) si n >= 4.
réponse 3 : voir dessus
réponse 4 : c'est faux. le 1er cas "si n= 0 ou n = 1 table[n] = n" est fantaisiste et n'a aucun rapport avec l'énoncé.