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