calcul de complexité itératif ou algorithmique

Bonsoir à tous,

Je suis dans l'étude de la notion de complexité pour une boucle ou un algorithme.
Il s'agit, par exemple, de savoir ou plutôt de calculer le nombre d'itération nécéssaire pour le tri d'un tableau.

Je comprend le principe à peu près mais je bloque sur un calcul simple exposé en exemple dans mon livre.Je vous réécris la parti qui me pose problème:

===========================================================
Approche Théorique

Calculons la complexité théorique du tri par sélection dans des cas simples. Supposons pour cela que le tableau à trier possède N éléments. Déterminons le nombre de comparaisons effectuées en fonction de N.

Pour trouver l'élément le plus petit, il faut parcourir tout le tableau. Cette opération est effectuée N-1 fois, avec au début N éléments, puis N-1 éléments, puis N-2 éléments, jusqu'a ce qu'il ne reste que 2 éléments(quand il n'en reste qu'un, il n'y a plus de parcours à faire). Calculons le nombre de parcours du tableau:

nombre de parcours = N + (N - 1) + (N - 2) + ... + 3 + 2
= N x (N - 1) / 2 : le terme le plus grand de l'expression
N x (N - 1) / 2 est N² / 2 = 0,5 x N².On retrouve alors
l'expression calculée par l'approche pratique.

==========================================================

-Pourquoi à la fin de la 1e expression on a 3 + 2 ca correspond a quoi ?

-Si je prend pour exemple un tableau de 10 indice je trouve 54 pour la 1e expression( N + (N - 1) + (N - 2) + ... ) mais pour la 2 expression( N x (N - 1) / 2) je trouve 45. ou me suis je trompé ?



Merci à vous pour votre précieux éclairage ;)

Citation:

---

Envoyé par miltone

Bonsoir à tous,

-Pourquoi à la fin de la 1e expression on a 3 + 2 ca correspond a quoi ?

---

Ca correspond aux deux derniers parcours du tableau quand il ne reste plus que 3 puis 2 éléments.

Citation:

---

-Si je prend pour exemple un tableau de 10 indice je trouve 54 pour la 1e expression( N + (N - 1) + (N - 2) + ... ) mais pour la 2 expression( N x (N - 1) / 2) je trouve 45. ou me suis je trompé ?
[/B]

---

Heu pour moi :
n + n-1 + n-2 + ... = (n)*(n+1) / 2
et pas n - 1

Bonjour,

Citation:

---

Envoyé par pasdeface

Heu pour moi :
n + n-1 + n-2 + ... = (n)*(n+1) / 2
et pas n - 1

---

Oui tu as raison sur le calcul. Mais...
En fait lorsque tu cherches ton minimum, tu initialises ta variable min avec le premier élément, donc il ne te reste plus qu'à parcourir les n-1 éléments réstants. Donc la formule de la somme des N-1 éléments est n(n-1)/2.

Citation:

---

Citation:
Envoyé par miltone Voir le message
Bonsoir à tous,

-Pourquoi à la fin de la 1e expression on a 3 + 2 ça correspond a quoi ?
Ça correspond aux deux derniers parcours du tableau quand il ne reste plus que 3 puis 2 éléments.

---

Ça peut effectivement être cela mais dans ce cas c'est mal dit puisque il aurait été plus pratique d'écrire (N - 7) donc 3 restant et (N - 8) donc 2 restant.

Ok pour cela c'était pas mon soucis principale j'ai compris ;)



Sinon suis-je le seul à trouver 2 valeurs différentes pour les 2 expressions de calcul de nombre de parcours(par exemple 10) ?

Citation:

---

Envoyé par miltone

Ça peut effectivement être cela mais dans ce cas c'est mal dit puisque il aurait été plus pratique d'écrire (N - 7) donc 3 restant et (N - 8) donc 2 restant.

---

Surtout pas.
Enfin si pour n = 10
Mais pour n quelconque ça ne finit pas à N - 8

Citation:

---

Sinon suis-je le seul à trouver 2 valeurs différentes pour les 2 expressions de calcul de nombre de parcours(par exemple 10) ?

---

Comme Toto13 l'a expliqué on commence le parcours avec n-1 éléments à parcourir, donc la somme est bien égale à n*n-1 / 2
Et si tu calcule pour n = 10, il faut faire 9 + 8 + ....

Citation:

---

Comme Toto13 l'a expliqué on commence le parcours avec n-1 éléments à parcourir, donc la somme est bien égale à n*n-1 / 2
Et si tu calcule pour n = 10, il faut faire 9 + 8 + ....

---

D'après mon livre que j'ai cité plus haut:
-Cette opération est effectuée N-1 fois donc 9 fois pour un tableau de 10
-avec au début N éléments donc 10

donc cela donnerais d'après moi
10+9+8+7+6+5+4+3+2(N - 1 éléments commencant à N) = 54
et cela donnerais d'après toi
9+8+7+6+5+4+3+2+1(N - 1 éléments commencant a N -1) = 45
ce qui effectivement tombe juste mais pourquoi on inclu le 1 alors que celui dit
"jusqu'a ce qu'il ne reste que 2 éléments(quand il n'en reste qu'un, il n'y a plus de parcours à faire)."
Apparement le 1 ne doit pas être compter puisque il n'y a plu de parcours a faire et pourtant le calcul tombe juste?

Donc finalement j'ai compris ce que vous m'avez dit et je pourrais le refaire bêtement sans problème et trouver la solution mais je n'aurais toujours pas compris la philosophie du truc qui pourtant n'a pas l'air compliqué.

Je penses que le la formule utilisée est pour n-1 à 1, alors que dans ce problème cela va de n-1 à 2, mais ça ne fait pas une grosse différence et c'est négligeable.
En complexité ce n'est pas important.

merci de tes réponses pasdeface

Citation:

---

alors que dans ce problème cela va de n-1 à 2

---

Oula non dans ce problème cela vaut aussi de n-1 a 1 si on veut tombé juste et même si on suis ce que dit le livre cela serais plutôt de n à 2.Mais dans tous les cas ca tombe faux.

par contre

Citation:

---

Je penses que le la formule utilisée est pour n-1 à 1

---

Il faut que je fasse d'autre essai avec d'autre tableau mais je pense que au final la bonne formule est celle-ci effectivement puisque cela marche aussi avec 20.

Même si cela n'est pas très important et change peut je note encore une fois que mon livre est encore faux!ca deviens vraiment acassant à la fin!



Grand merci à toi pasdeface ;)
en esperant pour toi qu'un jour tu retrouve ta face quand même :lol:

Je viens de me rendre compte qu'il y a quelques chose qui ne va pas si on commence par N - 1

Car après c'est la formule N x (N - 1) / 2 qui ne va plus car l'élément le plus grand n'est plus N tous court mais bien N - 1 donc N² ne peut donc pas existé et donc la proportionnalité 0,5 x N² ne peut être construite.

Donc la théorie de commencer a N - 1 et finir a 1 tiens pour le calcul théorique mais ne tiens plus pour le calcul avec N x (N - 1) / 2

et

pour la théorie de commencer à N et de finir à N - 1 tiens pour le calcul N x (N - 1) / 2 mais pas pour le calcul théorique


Vraiment je suis dans l'impasse là

Tu as N éléments au départ.

Au début tu dois parcourir ta liste et comparer le premier élément avec n-1 éléments pour trouver le minimum.
A l'étape d'après n-2 éléments
etc...
ce qui fait n-1 + n-2 + n-3 .... = n * (n-1) / 2
Qu'est ce qui te gêne?

Bonjour,
l'auteur s'est permis quelques raccourcis qu'on l'ont conduit à se tromper pour arriver au bon résultat:
Fait:
1+2+3+.....n-1+n = n(n+1)/2

corrigeons et précisons l'énoncé

Citation:

---

Envoyé par miltone

Bonsoir à tous,
[I]Approche Théorique

Calculons la complexité théorique du tri par sélection dans des cas simples. Supposons pour cela que le tableau à trier possède N éléments. Déterminons le nombre de comparaisons effectuées en fonction de N.

Pour trouver l'élément le plus petit, il faut parcourir tout le tableau. Cette opération est effectuée N-1 fois, avec au début N éléments, puis (N-2 opérations pour) N-1 éléments, puis N-2 éléments, jusqu'a ce qu'il ne reste que 2 éléments(quand il n'en reste qu'un, il n'y a plus de parcours à faire). Calculons le nombre de parcours du tableau:

nombre de parcours = (N - 1) + (N - 2) + ... + 3 + 2 +1
(et pas N +)
= ( N x (N -1) )/ 2
-1 est négligeable devant N (edit corrections)
=> on est en o(n²/2)

---

On m'a appris à négliger également le facteur "/2", cela ne change pas l'ordre de grandeur par rapport aux autres tris en o(n²).

Note: on part de N-1 car pour comparer N éléments, on compare le 1er élément aux n-1 suivants => n-1 opérations.
donc ce n'est plus n*(n+1)/2 de 1.. à n mais bien n*(n-1) /2= n-1+ n-2+ ... +4+3+2+1
(edit suppressions)

Pour ton exemple de calcul de n=10 éléments, il faut partir de 9

Citation:

---

n=10
=10.0

n*(n-1)/2
=45.0

9+8+7+6+5+4+3+2+1
=45.0

---

Citation:

---

Envoyé par deltree

Note: on part de N-1 car pour comparer N éléments, on compare le 1er élément aux n-1 suivants => n-1 opérations.
donc ce n'est plus n*(n+1)/2 de 1.. à n mais bien n*(n-1) /2= n-1+ n-2+ ... +4+3+2+1
Mais on s'arrête en 2 donc j'ai ajouté à la formule "-1".

---

8O ??

Soit un tableau de 4 elements T4=[a,b,c,d] (pour l'exemple, en ordre decroissant)

step #1: min( min( min(a,b), c), d) = d --> 3 comparaisons
step #2: min( min(a,b), c ) = c --> 2 comparaisons
step #3: min(a,b) = b --> 1 comparaison
step #4: il ne reste que "a" --> 0 comparaison

Total 3 + 2 + 1 + 0 = 4*(4-1)/2 = 6 comparaisons

J'ai suivi l'énoncé d'abord :o
mais je me suis arrêté au fait qu'il partait de n au lieu de n-1, et pas qu'il s'arrêtait en 2 au lieu de 1 (en fait j'ai pas vérifié tout l'algo... :/)


donc dans l'énoncé ce qui est faux:

Citation:

---

N + (N - 1) + (N - 2) + ... + 3 + 2
= N x (N - 1) / 2

---

correction:

Citation:

---

(N - 1) + (N - 2) + ... + 3 + 2 + 1
= N x (N - 1) / 2

---

merci pseudo-code de cette ultime correction, je met à jour mon post précdent, ne soyez pas surpris. ;)

Grand merci à vous les gars d'avoir pris la peine de vous pencher un peu sur le truc.Surtout par la qualité de vos réponses détaillées.Vous ne m'avez pas aidé pour rien croyez moi.Encore une fois c'était une erreur venant du livre.

J'ai vérifié encore une fois et ça marche belle et bien et j'ai compris le truc.

Je vous souhaite une bonne soirée au plaisir de vous recroisez :king: