Discussion :

[nono_31]

Bonjour,

J'ai besoin d'aide pour calculer la complexité de deux boucles imbriquées avec une structure suivante :

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in k_1..k_n 
    ...
endfor
endfor

où k_1 + ... +k_n = n.

Je dirais que la complexité de ces boucles imbriquées est O(n) puisqu'on rentre n fois dans chacune des boucles.
J'aimerais que vous me le confirmiez et que vous m'indiquiez comment le prouver correctement.

Merci d'avance,
Arnaud

[souviron34]

eh bien c'est faux

Pour chaque itération de la boucle i, tu as k_n itérations de la boucle j.

Comme au total tu auras n itérations, tu auras donc une complexité en O(n*k_n).

Comme k_1+...k_n vaut n, ce sera donc O(n2)

[nono_31]

Oups,

Je suis désolé, une erreur s'est glissée dans le pseudo-code. Il fallait lire :

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in 1..k_i 
    ...
endfor
endfor

et toujours k_1+...+k_n = n.

Donc, je voudrais montrer que :
-1ère itération de la boucle i : k_1 opérations
-2ème itération de la boucle i : k_2 opérations
...
-n-ème itération de la boucle i : k_n opérations

Merci.

[souviron34]

comme me l'a rappelé si bien Nebulix ici

1+2+3+...+n=n*(n-1)/2 ~O(n²)

Donc ta double boucle est donc bien en O(n2)..

[nono_31]

Merci pour la réponse, mais je ne suis toujours pas convaincu.
Votre formule est valable pour une boucle de la forme :

Code :

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

1
2
3
4
5
for i in 1..n
    for j in 1..i 
    INSTR
endfor
endfor

puisque dans ce cas là, on a :
-1ère itération de la boucle i : 1 opérations
-2ème itération de la boucle i : 2 opérations
...
-n-ème itération de la boucle i : n opérations
Soit un total de 1 + 2 + ... + n = n(n+1)/2 (et non n(n -1)/2)

[souviron34]

Soit un total de 1 + 2 + ... + n = n(n+1)/2 (et non n(n -1)/2)

ça s'appelle se tirer dans le pied

n(n-1)/2 = n2/2 -n/2

Comme on n'est pas à une constante près, c'est dominé par n2


Que ce soit n(n-1)/2 ou n(n+1)/2...

[nono_31]

Bon évidemment, je ne dois pas être très clair.

Que ce soit n(n-1)/2 ou n(n+1)/2...

Je voulais juste corriger la formule de Gauss sur la somme des nombres de 1 à n.
Pour la petite histoire, un professeur fatigué désirant un moment de tranquillité et demande à ses élèves de sommer les nombres de 1 à 100.
Il est très surpris quand le jeune Gauss lui présente le résultat 5mn plus tard.
Cette formule repose sur l'observation suivantes :
1 + n = n+1
2 + (n -1) = n+1
...
k + (n-k+1) = n+1
...
(n-1) + 2 = n+1
(n) + 1 = n+1
Soit un total de n(n+1)/2

Ensuite, la formule de Gauss s'applique à une boucle de la forme :

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in 1..i 
    INSTR
endfor
endfor

Mais pas dans mon cas :

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in 1..k_i
    INSTR
endfor
endfor

où k_1+...+k_n = n.

[souviron34]

Mais pas dans mon cas :

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in 1..k_i
    INSTR
endfor
endfor

où k_1+...+k_n = n.

je re-répète :

à chaque itération i, tu fais k_i itérations...

C'est donc borné par n..

Et la complexité est la borne...

[nono_31]

Je comprends votre raisonnement :

Raisonnement 1
boucle i : O(n)
boucle j : k_i < n -> O(n)
une borne supérieure sur la complexité au pire cas est O(n^2).

Raisonnement 2
Mais, je crois qu'une analyse plus fine montre que ces deux boucles imbriquées sont équivalentes au parcours d'un tableau T en deux dimensions où

Code :

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

1
2
3
4
5
6
7
8
9
 
T = [
[1, ..., k_1],
[1, ..., k_2]
...
[1, ... , k_i],
...
[1, ..., k_n]
];

On considère que T[i] =null si la valeur de k_j est 0.
Le tableau T a (k_1 + ...+ k_i+ ... + k_n) éléments, soit n éléments.
La complexité d'un tel parcours est O(n).

Ma question est donc : est-il possible de contredire le raisonnement 2 ?

[Acrim]

Bonjour, je ne veux pas trop m'éloigner du sujet initial mais les paramètres me laisse un peu perplexe.

où k_1 + ... +k_n = n.

Autrement dit, pour tout j dans [1,n] k_j = 1 ? (en supposant que les k_j sont des entiers positifs)

[nono_31]

Autrement dit, pour tout j dans [1,n] k_j = 1 ? (en supposant que les k_j sont des entiers positifs)

Non, on suppose que 0 <= k_i <= n.
Si k_i = 0, la condition entrée dans la boucle n'est pas vérifiée.
Pour le tableau, si k_i = 0, alors on considère que T[i] est l'élément null.

[pseudocode]

Code :

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

1
2
3
4
5
6
 
for i in 1..n
    for j in 1..k_i 
    ...
endfor
endfor

et toujours k_1+...+k_n = n.

Ca me semble équivalent à ca

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
@call mafonction(k_1) // effectue k_1 fois l'operation
@call mafonction(k_2) // effectue k_2 fois l'operation
@call mafonction(k_3) // effectue k_3 fois l'operation 
...
@call mafonction(k_n) // effectue k_n l'operation
 
func mafonction(k) // effectue k fois l'opération
  for j in 1..k
    /* operation */
  endfor  
endfunc

Au total on effectue donc k_1+...+k_n = n fois l'opération.

[nono_31]

Merci pour cette confirmation