Bonjour,
y a t il kelkun qui pouré me dire la compléxité d'un tel algithme, et la methode kil utilise pour la trouver :
pour i allant de 1 a n par pas de 1 faire
pour j allant de i à 2*i par pas de 1 faire
p:=0
finpour
finpour
merci
-----
21/12/2006, 22h31
#2
Nicolas666666
Date d'inscription
juillet 2005
Localisation
Toulouse (étude)
Âge
22
Messages
592
Re : Complexité d'algorithme
peux tu expliquer plus ton message? le language sms est interdit au fait et en plus on ne comprend pas ce que tu dis
21/12/2006, 22h41
#3
invite84c98a4b
Date d'inscription
janvier 1970
Messages
4
Re : Complexité d'algorithme
alors voila, je voudrais savoir le temps d'execution aproximatif d'un tel algorithme...
merci
21/12/2006, 22h42
#4
azt
Date d'inscription
janvier 2003
Localisation
Au sud de Paris, t'y es.
Âge
44
Messages
926
Re : Complexité d'algorithme
Bonsoir,
ton programme ne veut pas dire grand chose, il doit être incomplet.
Dans quel sens parles-tu de complexité ?
Cordialement,
AZT
Nous sommes toujours de la taille de l'univers que nous découvrons. [Frédérick Tristan]
Aujourd'hui
A voir en vidéo sur Futura
22/12/2006, 00h47
#5
invite9cf21bce
Date d'inscription
janvier 1970
Messages
332
Re : Complexité d'algorithme
Salut !
On suppose qu'à chaque passage le programme effectue un nombre fini d'opérations, minoré par un entier k et majoré par un entier K.
Ici par exemple :
une opération pour initialiser i
une opération pour incrémenter i
une opération de test de i
une opération pour initialiser j
une opération pour incrémenter j
une opération de test de j
une opération de mise de p à 0
plus une dizaine d'opérations pour faire les sauts nécessaires
Disons k=1 et K=20, grossièrement.
Toutes les opérations citées ne sont pas effectuées à chaque passage (par exemple, l'incrémentation de i n'a lieu que quand on sort de la boucle sur j), mais ça n'a pas d'importance puisqu'on veut un majorant et un minorant.
Comme on effectue 2+3+4+...+(n+1)=(n+1)(n+2)/2-1 passages, on peut estimer que le nombre d'opérations effectuées N est compris entre an=(n+1)(n+2)/2-1 et
bn=20((n+1)(n+2)/2-1).
Maintenant, mathématiquement on a (n+1)(n+2)/2-1 ~ n2/2 lorsque n tend vers l'infini.
Donc N est compris entre deux nombres qui sont respectivement équivalents à n2/2 et 10n2. C'est donc un algorithme en n2.
Oublions le minorant. N est majoré par bn ~ 10n2. Donc N=O(n2). C'est donc un algorithme en O(n2).
En termes de complexité, tout dépend de la taille d des données :
Si tes données, c'est juste n, alors la taille des données est d ~ log2(n) (puisqu'un entier n est représenté par environ log2(n) bits), donc l'algorithme est en O((exp2(d))2)=O(exp2(2d)), il est exponentiel.
Si tes données sont de taille n où à peu près (c'est à dire d ~ C.n où C est une constante), ce qui est le cas par exemple si tu as un tableau à n entrées, alors l'algorithme est en O(d2), il est polynomial.
Le lien entre le nombre d'opérations N et le temps T nécessaire pour les effectuer est supposé être un lien de la forme N ~ D.T où D est une constante (c'est-à-dire que N et T sont (à peu près) proportionnels). Donc tout ce qui a été dit sur N se répète pour T.
23/12/2006, 18h08
#6
invite84c98a4b
Date d'inscription
janvier 1970
Messages
4
Re : Complexité d'algorithme
Bonjour,
merci bien Taar pour cette explication bien argumenté...
cordialement
23/12/2006, 22h00
#7
invite84c98a4b
Date d'inscription
janvier 1970
Messages
4
Re : Complexité d'algorithme
merci, mais j'arrive pas à l'appliqué a d'autres algorithmes. pas resemple :
i:=n;
tantque i>0 faire
si i mod 2 =1 alors
i:=i-1
sinon
i:=i/2
finsi
fin tantque
(et j'en ai d'autres encor, alors je n'arretré mé message que un efois ke j'auré comment ca marche )