Complexité d'algorithme

[invite84c98a4b]

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

[invite7fcbff32]

peux tu expliquer plus ton message? le language sms est interdit au fait et en plus on ne comprend pas ce que tu dis

[invite84c98a4b]

alors voila, je voudrais savoir le temps d'execution aproximatif d'un tel algorithme...
merci

[azt]

Bonsoir,
ton programme ne veut pas dire grand chose, il doit être incomplet.
Dans quel sens parles-tu de complexité ?

Cordialement,
AZT

[A voir en vidéo sur Futura]

[invite9cf21bce]

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 a_n=(n+1)(n+2)/2-1 et
b_n=20((n+1)(n+2)/2-1).

Maintenant, mathématiquement on a (n+1)(n+2)/2-1 ~ n²/2 lorsque n tend vers l'infini.
Donc N est compris entre deux nombres qui sont respectivement équivalents à n²/2 et 10n². C'est donc un algorithme en n².

Oublions le minorant. N est majoré par b_n ~ 10n². Donc N=O(n²). C'est donc un algorithme en O(n²).

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 ~ log₂(n) (puisqu'un entier n est représenté par environ log₂(n) bits), donc l'algorithme est en O((exp₂(d))²)=O(exp₂(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(d²), 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.

[invite84c98a4b]

Bonjour,

merci bien Taar pour cette explication bien argumenté...

cordialement

[invite84c98a4b]

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 )