complexité d'un algorithme recursif

kali.009

complexité d'un algorithme recursif

Message par kali.009 » 16 déc. 2016 23:54

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

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par fakbill » 18 déc. 2016 14:24

D'où sort ton -1/8?
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

007

Re: complexité d'un algorithme recursif

Message par 007 » 19 déc. 2016 22:32

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.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par fakbill » 20 déc. 2016 19:30

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é.

Messages : 3901

Inscription : 04 sept. 2005 19:27

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par JeanN » 20 déc. 2016 21:42

[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 :)
Professeur de maths MP Lycée Sainte-Geneviève

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par fakbill » 21 déc. 2016 18:32

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é.

Messages : 0

Inscription : 19 déc. 2014 17:35

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par CendreWapiti » 27 déc. 2016 00:44

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.
2014 - 2015 : MPSI2
2015 - 2016 : MP*
X 2016

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: complexité d'un algorithme recursif

Message par fakbill » 27 déc. 2016 16:59

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é.

Répondre