Complexite et grandeur asymptotique
tshuka
-
tshuka -
tshuka -
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
Tshuka
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
Tshuka
A voir également:
- Complexite et grandeur asymptotique
- Regle vrai grandeur - Guide
- Grandeur iphone 14 - Guide
- Tableau ordre de grandeur - Guide
- Complexité - Forum VB / VBA
- Grandeur UserForm ✓ - Forum VB / VBA
4 réponses
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 te conseille de faire tourner l'algo avec un n petit genre 4.
Déroule le et tu vois au niveau des boucle le nombre de passage.
étape 1:
i = 1
j = 2 j=3 j=4
k = 1 k=1 k=1
k = 2 k=2 k=2
k=3 k=3
k=4
donc tu vois que
tu es passé dans la troisième boucle tu passe j fois
tu es passé dans la deuxième boucle (n-1) étape 1, tu passera n-2 a l étape 2 soit
(n-i) et ceux somme(i=1,i=n-1) (n-i)
soit au total somme(i=1,i=n-1) (n-i) * j avec j = (a trouver)
bref, j'espère qu tu vois l'idée, ca fait longtemps j'en ai pas fait, j 'espère t'aiguiller
faire pour j de i+1 a n
faire pour k de 1 a j
faire {instruction}
je te conseille de faire tourner l'algo avec un n petit genre 4.
Déroule le et tu vois au niveau des boucle le nombre de passage.
étape 1:
i = 1
j = 2 j=3 j=4
k = 1 k=1 k=1
k = 2 k=2 k=2
k=3 k=3
k=4
donc tu vois que
tu es passé dans la troisième boucle tu passe j fois
tu es passé dans la deuxième boucle (n-1) étape 1, tu passera n-2 a l étape 2 soit
(n-i) et ceux somme(i=1,i=n-1) (n-i)
soit au total somme(i=1,i=n-1) (n-i) * j avec j = (a trouver)
bref, j'espère qu tu vois l'idée, ca fait longtemps j'en ai pas fait, j 'espère t'aiguiller
