Niveau Licence Maths 1e ann

complexite d'un algorithme

Posté par
thotoss 27-11-08 à 22:46

Bonjour,
je cherche a calculet la complexite f(n) de l'algorithme suivant :

pour i de 1 a n-1
faire pour j de i+1 a n
faire pour k de 1 a j
faire {instruction}

Je suppose que Instruction a un temps constant c. Et je voudrais aussi en deduire l'ordre de grandeur asymptotique ... j'avoue que je bloque pas mal je comprend pas trop comment partir en fait, j'espere que vous pourrez un peu m'aider !
Merci d'avance!
Cordialement

Posté par complexité d'un algorithme 28-11-08 à 02:27

salut

tu executes:
n-1 fois la première boucle
n-i fois la 2e boucle
j fois la 3e boucle

ça doit faire pas loin de n³

mais bon vu le croisement des indices (les intervalles "croisés des variables, c'est peut-être du n²

en tout cas ça doit être entre les deux (à affiner)
ce me semble-t-il