Discussion :

[ikeita20]

Bonjour tout le monde j'ai un problème dans le calcul de la complexité de ce algorithme; je suis débutant et je jai vraiment du mal a comprendre comment ça marche le truc, je ne sais pas combien de fois sont executées mes boucles imbriquées et combien de fois on passe par chaque boucle .


Variables locales

tab : tableau[n][m] de réels
i, j, k, compteur : entiers

Début
compteur ← 0
Pour i allant de 1 à n par pas de 1 faire
Pour j allant de 1 à m par pas de 1 faire
tab[i][j] ← 0
Pour k allant de i à j par pas de 1 faire
tab[i][j] ← tab[i][j] + 1
compteur ← compteur + 1
Fin pour
Fin pour
Fin pour
Fin

[wiwaxia]

Bonjour,

Une indentation du texte - éventuellement son annotation - mettent en valeur la structure du programme, et te permettraient peut-être de mieux comprendre ce qu'il effectue:

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
Variables locales

tab : tableau[n][m] de réels
i, j, k, compteur : entiers

Début
  compteur ← 0
  Pour i allant de 1 à n par pas de 1 faire          // Pour 1
    Pour j allant de 1 à m par pas de 1 faire           // Pour 2      
      tab[i][j] ← 0
      Pour k allant de i à j par pas de 1 faire            // Pour 3
        tab[i][j] ← tab[i][j] + 1
        compteur ← compteur + 1
      Fin pour                                             // Fin 3
    Fin pour                                           // Fin 2 
  Fin pour                                          // Fin 1
Fin

1) Combien y a-t-il de boucles ? Sont-elles successives ou imbriquées ?
2) Détailler ce qui se passe dans un cas particulier, par exemple: n = 3 et m = 2 :
a) faire un tableau de (m*n) = 6 cases;
b) noter l'initialisation du tableau;
c) compter les incrémentations imposées à l'élément [I]tab[j], et celles concernant le compteur.

Je me demande d'ailleurs ce qu'il arrive dans le cas où l'on a (i > j), et par exemple:

Code :

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

Pour k allant de 3 à 1 par pas de 1 faire

Le pas vaut alors (-1); est-il simplement défini en valeur absolue ? Regarde les règles que l'on t'a données.