Bon visiblement j'ai mal attaché la fonction.

Première double boucle :

i varie de 1 à n
   j varie de 0 à 1,  donc 2 X
   j varie de 0 à 3,  donc 4 X
   j varie de 0 à 5,  donc 6 X
   ...
   j varie de 0 à 2i-1,  donc 2i "X"
   ...
   j varie de 0 à 2n-1,  donc 2n "X"

Donc X est affiché :  

Deuxième double boucle :

Il y a un "piège", car le PUTCHAR("X") n'est pas dans la sous-boucle sur j.
Il faut donc compter la simple boucle sur i...

i varie de 1 à n, donc n "X".

Au total :  N = n.(n+2)

... à vérifier par toi même bien sûr ...

Merci pour la réponse, j'ai toutefois une question. L'exercice suivante me semble quasiment identique.

Si à la place de la boucle for j'avais la boucle while de la façon suivante:

for (i=1; i<(n-1); i++) {
  j=i-1
  while ( j>=0) do
  {
     put("X");
     i--;
  }
}

Aurais je même résultat?

La première ligne de la fonction est for (i=1; i<=(n-1); i++) { et non for (i=1; i<(n-1); i++) {

En fait il s'agit partiellement du tri insertion que j'ai essayé de traduire en JAVA, c'est un peu raté...

Je ne comprends pas le résultat final:

pour la boucle j
on a j varie de n-1 à 0   donc  n  "put X"
donc somme de j pour j allant de 0 à n-1
donc ((n-1)(n-1 +1))/2 = n(n-1) / 2

pour la i
on a i qui varie de 1 à n-1
donc (n-2)

donc au total:
n(n-1)(n-2) / 2

Où est ce que je me suis trompé?

Et de toutes manières il n'y a jamais 3 boucles imbriquées...
Donc peu d'espoir d'avoir une formule d'ordre 3.

Tu ne crois pas ?

Oui tu avais raison pour la boucle, la fonction que tu avais réécrit était bonne.
Pour mon calcul, je suis partie de ton raisonnement: en supposant i varie de 1 à n-1 et  j varie de n-1 à 0   donc  n  "put X" (comme tu l'avais dit) mais je n'ai pas réussi à trouver  N = n.(n+1)/2 en résultat final mais plutôt n(n-1)(n-2) / 2 .


En fait il s'agissait de trouver le nombre maximal et minimal de comparaison entre éléments du tableau (donc le nombre de fois où l'instruction de la ligne 5 est exécuté) pour le tri insertion ci dessous.

J'ai fait le rapprochement entre les deux exercice donc j'ai supposé que le résultat serait identique à celle de boucle.

Je viens de recalculer, je pense que ce serait

somme de i pour i allant de 0 à (n-1) = ((n-1)n) / 2  non?

Rectificatif et précision :

Le code que tu as présenté en dernier réalise un TRI PAR INSERTION.
Sa performance est à peu près équivalente à celle du TRI A BULLE.

Au pire, comme je l'ai dit, si tu parcours la boucle intérieure systématiquement (parce que la deuxième condition (A(i)>key) est systématiquement vraie...), alors la complexité sera en n(n-1)/2...  La boucle intérieure sera exécutée systématiquement si le tableau est trié "à l'envers" au départ. C'est un cas extrême qui n'arrive presque jamais (le "pire cas").

De même et réciproquement, la boucle intérieure peut ne jamais être exécutée (deuxième condition jamais vraie). Dans ce cas, également extrême, et donc également "rare", la complexité sera en  n-1...  Ce cas correspond à un tableau déjà trié dans le bon ordre (le "meilleur cas").

Dans le cas général, la boucle sera exécutée "en moyenne" une fois sur deux. Parce que grosso modo, deux nombres pris au hasard dans le tableau de départ, ont la même chance d'être "le plus grand des deux"... ce qui implique une probabilité 1/2 pour la boucle intérieure de s'exécuter.

Au final, pour un tableau ordonné aléatoirement, il y a donc en moyenne une complexité de l'ordre de  n²/4  (la moitié du pire cas).

Bonjour,

Quelqu'un pourrait confirmer ma résolution de l'exercice ci dessous?

Cet algorithme utilise deux comparaisons différentes. Il y a i > 0, qui est toujours une comparaison d'entiers (donc toujours effectuée en temps constant), et A[i] > key qui compare les éléments stockés dans le tableau, et dont la complexité dépend de la nature de ces éléments (entiers, chaînes de carac- tères, enregistrements de base de données, etc.). Par la suite, nous ne nous intéressons qu'à ces dernières comparaisons, entre les éléments du tableau.

On note n la taille du tableau A, dont les indices vont de 0 à n − 1.

1. Quel est le nombre maximal de comparaisons (entre éléments du tableau) effectuées par INSERTIONSORT ? Donnez une réponse précise en fonction de n.

2. Quel est le nombre minimal de comparaisons (entre éléments du tableau) effectuées par INSERTIONSORT ? Donnez une réponse précise en fonction de n.

3. Quelle est la complexité de INSERTIONSORT dans le pire cas, lorsque les éléments à trier sont des entiers ?

4. Étant donné deux chaînes de n caractères, quel est la complexité de l'algorithme qui com- pare les deux chaînes pour décider laquelle vient avant l'autre dans l'ordre alphabétique ? (C'est la fonction strcmp() en C.)

5. Déduisez-en la complexité de INSERTIONSORT dans le pire cas, lorsque le tableau contient n chaînes de caractères de taille n à trier dans l'ordre alphabétique.



Voici mes réponses:

1) somme de i pour i allant de 0 à (n-1) = ((n-1)n) / 2.

2) dans le pire le tableau est trié donc A[i]>key n'est jamais valide donc le nombre minimal de comparaison est n.

3) la ligne 2, 3 et 7 seront exécuté n fois
la boucle est exécuté, dans le pire cas, ((n-1)n) / 2 fois
donc en somme 3n + ((n-1)n) / 2 fois
j'en déduit que la complexité est de Θ(n^2)

4) je compare chaque caractère de même indice donc la complexité est en Θ(n)

5) la boucle est exécuté ((n-1)n) / 2 fois
la complexité de strcmp est Θ(n)
la complexité des instructions sont en Θ(1)
donc complexité de insertionSort avec strcmp est de Θ((n-1)n) / 2 max(Θ(n), Θ(1)) = Θ(n^3)


Merci d'avance



*** message déplacé ***

Bonjour,

Sais tu que le multipost = poster plusieurs fois le même sujet est interdit ici ?

Trois fois c'est beaucoup....

*** message déplacé ***