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
Configuration: Windows XP Firefox 3.0.4
A voir également:
- Complexite et grandeur asymptotique
- Regle vrai grandeur - Guide
- Iphone 14 grandeur - Guide
- Combien y a t-il de ko dans un go (ordre de grandeur) ? - Forum Mobile
- Les ko=combien de Go ✓ - Forum Windows
- Combien fai 1 gb en ko ?, ✓ - Forum Windows
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
