Discussion :

[taha120]

bonjour je voudrais savoir comment je peux déterminer la complexité temporelle de cet algorithme dans les cas favorable, défavorable et moyen. et merci d'avance pour vos réponses


Soit A un vecteur d’entiers. Soit la fonction suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
void function mystere(int k) {
    int p=0 ; bool m;
    if (k != 0) {
        mystere(k-1) ;
        m=false ;
        int i = k-1 ; int temp = A[k] ;
        while ( i >= 0) and (temp >= A[i]) {
            A[i+1] = A[i] ; p = i ; m=true ; i = i-1 ;
        }
        if (m)
            A[p] = temp ;
    } //fin du if
}

[WhiteCrow]

Bonjour,
déjà il faut bien indenter ton code pour qu'il soit lisible et donne envie de le lire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
void function mystere(int k) {
  int p = 0;
  bool m;
  if (k != 0) {
    mystere(k - 1);
    m = false;
    int i = k - 1;
    int temp = A[k];
    while (i >= 0)
      and(temp >= A[i]) {
        A[i + 1] = A[i];
        p = i;
        m = true;
        i = i - 1;
      }
    if (m)
      A[p] = temp;
  } // fin du if
}

La complexité temporelle (en considérant les instructions en O(1)) sera dépendante de l'appel récursif et de la boucle while.
Les questions à se poser sont donc :

• combien d'appels récursifs sont-ils faits ?
• à chaque appel récursif combien de fois la boucle while sera-t-elle déroulée (au pire, au mieux) ?