Complexité C++

Voici l'algorithme du Tri Bulle :

Tri_bulle (t[1....n]) :

1: i <- 1
2: tant que i <- n-1 faire

3: j <- n
4: tant que j -> i+1 faire

5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1


La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de fois
où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en fonction
de n et k.

La réponse etant;

"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "

Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si n
reprénsente la taille du tableau, alors le nombre de comparaison est égal à
n- 1 à chaque passage dans le tableau. On compare un element avec les autres
element.... excepté lui même . Mais mon problème etant que je ne comprends
pas ce raisonnement.

On Mon, 17 May 2004 12:11:53 +0400, "BuG" <bug@asrun.org> wrote:

Voici l'algorithme du Tri Bulle :

Tri_bulle (t[1....n]) :

1: i <- 1
2: tant que i <- n-1 faire

2: tant que i <= n-1 faire

3: j <- n
4: tant que j -> i+1 faire

4: tant que j >= i+1 faire

5: si t[j] < t[j -1] alors
6: valeur <- t[j]
7: t[j] <- t[j -1]
8: t[j -1] <- valeur
9: j <- j-1
10:i <- i+1


La question etant :
Soit n la taille du tableau à trier et k la valeur de la variable i à
l'entrée dans la deuxième boucle "tant que". Soit C(n,k) le nombre de
fois

où la comparaison de la ligne 5 est effectuée. Exprimez C(n,k) en
fonction

de n et k.

La réponse etant;

"C(n,k) = n - (k +1) +1"
"C(n,k) = n-1 "

Deux réponses?. Èvidemment C(n,k) = n-k, c.a.d C(n.1) = n-1.


*********************

Ma question :
En regardant des exemples de tri bulle, on s'aperçoit facilement que si
n

reprénsente la taille du tableau, alors le nombre de comparaison est
égal à

n- 1 à chaque passage dans le tableau. On compare un element avec les
autres

element.... excepté lui même . Mais mon problème etant que je ne
comprends

pas ce raisonnement.

Je ne comprends pas ce que veut dire "en regardant des exemples...".
Dans l'algorithme que tu as décrit il y a n-1 comparaisons dans la
premiere boucle i (i=1) n-2 dans la seconde (i=2),..., et une dans la
derniere (i=n-1). Donc il y un nombre total de

1 + 2 + ... + n-1 = n(n-1)/2

comparaisons dans l'algorithe ci-dessus. Toujours.

--
Horst

En faite ma
question etait de savoir comment raisonner sur l'algo pour trouver que
C(n,k) = n - (k +1) - 1 = n-k
Je comprend pas comment on arrive à ce résultat...Le "n" s'est la taille du
tableau mais le "k+1" et le "+1". D'ou sortent il ??? :-)

On Mon, 17 May 2004 13:39:00 +0400, "BuG" <bug@asrun.org> wrote:

En faite ma
question etait de savoir comment raisonner sur l'algo pour trouver que
C(n,k) = n - (k +1) - 1 = n-k
Je comprend pas comment on arrive à ce résultat...Le "n" s'est la taille
du

tableau mais le "k+1" et le "+1". D'ou sortent il ??? :-)

Tu as n éleménts numérotés de 1 à n. Et i a une valeur entre 1 et n-1.


1 2 3 4 .... i i+1 ....... n
| <- j


maintenant tu compares à partir de j=n et descendant jusqu'à j=i+1
l'élément numéro j avec son prédésesseur numéro j-1. Il faut donc
compter les entiers de i+1 à n. Ce nombre est n-i. Formule générale:
Le nombre des entier de X à Y est Y-X+1 si X<=Y. Ici donc

n - (i+1) - 1 = n - i

--
Horst