Discussion :

[miltone]

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

[contremaitre]

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.

-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

[ToTo13]

Bonjour,

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.

[miltone]

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

[contremaitre]

Ç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

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

[miltone]

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

[deltree]

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é

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

n=10
=10.0

n*(n-1)/2
=45.0

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

[pseudocode]

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

??

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

[deltree]

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:

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

correction:

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

[miltone]

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