complexité d'un algorithme recursif
complexité d'un algorithme recursif
Bonjour
Je dois calculer la complexité suivante :
F(n) = 2*F(n/4) + 2*F(n/4 - 1/8) +1
Je sais qu'il faut transformer cette fonction en F pour pouvoir utiliser le master théorème mais j'arrive pas à faire cette transformation.
J'ai vu sur internet une généralisation du master théorème qui ne contient que des termes en n/a dans F avec a > 1, mais ici j'ai le terme -1/8 qui me pose problème.
Je vous remercie par avance
Je dois calculer la complexité suivante :
F(n) = 2*F(n/4) + 2*F(n/4 - 1/8) +1
Je sais qu'il faut transformer cette fonction en F pour pouvoir utiliser le master théorème mais j'arrive pas à faire cette transformation.
J'ai vu sur internet une généralisation du master théorème qui ne contient que des termes en n/a dans F avec a > 1, mais ici j'ai le terme -1/8 qui me pose problème.
Je vous remercie par avance
Re: complexité d'un algorithme recursif
D'où sort ton -1/8?
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: complexité d'un algorithme recursif
Je crois qu'il faut reprendre la définition de F qui doit être erronée : ici comme F n'a pas d'arrêt, elle a une complexité (théorique) infinie.
Re: complexité d'un algorithme recursif
de quoi?????????? F n'a pas d’arrêt?? Ca n'a aucun sens.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: complexité d'un algorithme recursif
[quote="fakbill"]de quoi?????????? F n'a pas d’arrêt?? Ca n'a aucun sens.[/quote]
Tout le monde est d'accord (sauf le posteur initial...), pas la peine de s'enflammer
Tout le monde est d'accord (sauf le posteur initial...), pas la peine de s'enflammer
Professeur de maths MP Lycée Sainte-Geneviève
Re: complexité d'un algorithme recursif
arf. applique une règle de réécriture qui remplace N ? en un seul ?
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: complexité d'un algorithme recursif
L'expression de F est bizarre.
Si c'est une complexité et n la taille de l'entrée, alors F est définie uniquement sur les entiers, et auquel cas l'expression de F n'a aucun sens.
Sinon qui est n ?
Au pire file ta fonction récursive.
Si c'est une complexité et n la taille de l'entrée, alors F est définie uniquement sur les entiers, et auquel cas l'expression de F n'a aucun sens.
Sinon qui est n ?
Au pire file ta fonction récursive.
2014 - 2015 : MPSI2
2015 - 2016 : MP*
X 2016
2015 - 2016 : MP*
X 2016
Re: complexité d'un algorithme recursif
oui d'où ma première question "d'où sort le -1/8"
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.