Bonsoir, je cherchais à approfondir mes connaissances jusqu'ici très basiques en calcul de complexité et voilà que je me heurte à un roc (que dis-je un roc... une péninsule) plus haut et bien plus costaud que ma personne :
T(n) = 2 * T(3*(n/4)) + T(n/4) + n
J'avoue que je ne sais pas par où attaquer des complexités avec des équations de récurrences, si quelqu'un pouvait me donner un tuyau afin de savoir par où commencer.
Merci d'avance,
Lilipletz
Donc mon idée principale était :
T(n) = a * T(n/b) + cn
Je sais que :
If a=b : T(n) = O(n.logn)
If a<b and c>0 : T(n) = O(n)
If a<b and c=0 : T(n) = O(logn)
If a>b : T(n) = O(nlogb(a))
J'écris T(n) = 2 T( n/(4/3)) + n + T(n/4)
a > b so T(n) = O(nlogb(a)) with a = 2 and b = 4/3
Donc il reste :
T(n) = O(nlog4/3(2)) + T(n/4)
De la même manière en m'occupant de T(n/4) , je trouve O(log(n))
Ce qui me laisserait donc avec une complexité de O(log(n)) + O(nlog4/3(2)) ??
Quel est ton problème ? Mathématique ou programmation ?
Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
Bonjour,
Merci de votre réponse
J'imagine un peu les deux, je ne vois pas si je choisis la bonne démarche pour trouver la complexité de cette equation de récurrence
Personne ?
Veux-tu que je déplace ton sujet en Mathématiques du supérieur ?
Rien ne sert de penser, il faut réfléchir avant - Pierre Dac
Volontiers, j'imagine qu'il y trouvera sa place =)
