[Complexité d'un algorithme] Triangle de Sierpinski

**Opérateur** · 16/12/2006, 20h43

Bonjour,

J'ai écrit un programme qui donne une représentation du triangle de Sierpinski dans une matrice n*n (n étant une puissance entière positive de 2). Les trous sont représentés par des caractères, les vides par des espaces, voici le code (c'est du C++ mais ça n'est pas bien méchant il n'y a que des boucles en gros) :

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
 
     int X = n;
 
     while (X > 1)
     {
           for (int i = 0; i < n; i+= X)
           {
               for (int j = 0; j < n; j+= X)
               {
                   for (int k = 0; k < X/2; k++)
                   {
                       for (int l = 0; l < X/2; l++)
                       {
                           C[i + k][j + X/2 + l] = ' ';
                       }
                   }
               }
           }
           X = X/2;
     }

Bon. Maintenant j'aimerais bien évaluer la complexité en fonction de n (en terme de grand O) de cet algorithme

Quelqu'un se sent d'attaque

? Moi j'ai essayé d'évaluer ça et je tombe sur une complexité en O(n^4)
Pour ce faire j'ai "simplement" évaluer la nombre de fois que chaque boucle for s'executait en fonction de n mais je pourrais bien m'être trompé

Quelqu'un sait-il me dire si c'est plausible/correcte ?

merci

**jobherzt** · 17/12/2006, 00h45

a mon avis, c'est beaucoup moins que ca. comment rentre tu les caracteres ?? on ne voit que les espaces..

**jobherzt** · 17/12/2006, 00h52

le bout que tu nous donnes est en O(log(n)*n^2/4), a priori.

**Opérateur** · 17/12/2006, 13h15

comment rentre tu les caracteres ?? on ne voit que les espaces..

Ah ça peut importe j'ai une matrice de caractère et je veux transformer cette dernière en une représentation du triangle de Sierpinski

Bon je vais essayer de comprendre ce que tu me donnes comme complexité, merci

**jobherzt** · 17/12/2006, 13h28

si ca t'interresse, voila comment je trouve ca :

si n=2^k, la boucle while principale efectue k tour, cad log2(n) (log en base 2).

concernant les 4 boucles a l'interieur, pour un X donné : les 2 premieres boucles vont de 0 a n par pas de X, donc tournent n/x fois chacune, les 2 suivantes vont de 0 a x/2 par pas de 1, donc tournent X/2 fois chacune. au total :

log2(n) * n/X * n/X * X/2 *X/2 = log2(n) * n^2 *(n^2)/4

**Opérateur** · 17/12/2006, 14h28

Ah merci bien d'avoir détaille le calcul

J'ai une grosse question, comment calculerais-tu la complexité du code suivant (X est supposé être une puissance entière de 2, disons 2^l pour fixé les idées) :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
 
while (X > 1)
{
     for (int i = 0; i < X/2; i++)
     {
          // Instructions en O(1) ...
     }
     X = X/2;
}

?

Moi j'essaie d'évaluer immédiatement le nombre de fois que la boucle for s'execute c'est à dire :

2^(l - 1) + 2^(l - 2) + 2^(l - 3) + ... 1 = (Somme de k allant de 1 à l) de (2^l / 2^k)

Après calcule de cette somme par une petite formule de math ça me donne 2^(l) - 1 soit une complexité en O(n)

Je me trompe ?

merci

**jobherzt** · 17/12/2006, 14h31

si ta formule de maths est juste, ca doit etre ca...

**jobherzt** · 17/12/2006, 14h37

en faisant un petit test avec n=1024, je trouve 2046 operations.. donc ca a l'air d'etre du O(2n), donc du O(n). ca m'a l'air bon !

**Opérateur** · 17/12/2006, 14h41

Oui j'ai utilisé la formule (il n'est pas possible d'utiliser Latex sur le forum ?)

(Somme pour k allant de 0 à n) x^k = (1 - x^(n + 1))/(1 - x)

Mais moi c'est ce même raisonnement que j'ai appliqué pour chacune des boucles donc ça me donne pour chaqune des 4 boucles for une complexité en O(n) donc j'ai à chaque fois multiplier ce qui me donne de l'O(n^4)

Je me trompe peut-être bien mais je ne vois pas pourquoi

merci

**Opérateur** · 17/12/2006, 14h58

Mais ça ne peut pas etre bon vu que j'ai testé avec différentes valeurs de n et n^4 c'est beaucoup trop

merci

**Opérateur** · 17/12/2006, 15h07

le bout que tu nous donnes est en O(log(n)*n^2/4), a priori.

J'ai testé et c'est exactement ça (chapeau

) mais je ne comprends paaaaass pourquoi ma solution est fausse

merci !

**Opérateur** · 17/12/2006, 16h18

Je pense que vu la manière dont X varie je ne peux pas simplement multiplier le nombre d'itérations de chaque boucle entre elles

Par exemple pour :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 int X = n;
 
     while (X > 1)
     {
                   for (int k = 0; k < X/2; k++)
                   {
                       for (int l = 0; l < X/2; l++)
                       {
                           // truc en O(1)
                       }
           }
           X = X/2;
     }

Le nombre de fois que le truc en O(1) est éxécuté est (n/2)^2 + (n/4)^2 + (n/8)^2 + ... ce qui au final donne (n² - 1)/3 executions (ça reste en O(n²) mais si on test sur de petites valeurs de n on ne s'en rend pas compte vu que la différence entre n² et (n² - 1)/3 est grande)
Il faudrait que je refasse le même calcul pour les deux autres boucles ...

**jobherzt** · 17/12/2006, 16h44

je t'ai donné le detail de mon calcul dans mon post de 12h28.. ta solution est fausse car tu fonctionne comme si chaque boucle faisait n iteration... et meme comme ca ca serait faux car tu ne tiendrais pas compte de la boucle while !! un truc en n^4 ca pourrait etre :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
for(i=0,i<n)
   for(j=0,i<n)
      for(k=0,i<n)
         for(l=0,i<n)
           (O(1))
         fin
      fin
   fin
fin

dans ton cas, tu n'as pas besoin d'appliquer de formule complexe, car les X se simplifient. en fait, l'idee c'est que si X est grand, les 2 premiere boucle vont faire peu de tour, et les 2 autres beaucoup, et le contraire si X est petit. donc quand certaine boucle deviennent plus importante, d'aure le devienne automatiquement mons, ca se compense. c'est pour a qu'on a une complexité faible meme avec 4 boucles.

conclusion : si, tu peux multiplier la complexité de chaque boucle, tu dois meme. mais elle ne sont jamais simultanement toute en O(n). donc ton resultat n'es pas faux, il est simplement un peu grossier, cad que tu prend "large".

**jobherzt** · 17/12/2006, 16h49

et accessoirement, dans ton dernier calcul non plus, j'ai l'impression que tu ne tiens pas compte de la boucle while, donc tu devrais multiplie par log2(n)

**Opérateur** · 17/12/2006, 19h07

D'accord merci bien pour l'explication !

Mais dans mon dernier calcul j'ai essayer en donnant des valeurs à n et j'ai tester ça me donne exactement (n² - 1)/3 itérations donc ça marche

merci bien !

**millie** · 17/12/2006, 21h57

Pour moi, c'était autre chose :

Code :

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

1
2
3
4
5
6
7
8
9
 int X = n;
 
     while (X > 1)
           for (int i = 0; i < n; i+= X)
               for (int j = 0; j < n; j+= X)
                  for (int k = 0; k < X/2; k++)
                    for (int l = 0; l < X/2; l++)
 
           X = X/2;

Dans le premier for, on fait : X/2 opération.
Dans les deux for, on en fait donc : X²/4.

Ensuite, les boucles i et j vont de X en X jusqu'à N, il y a donc n/X boucles.
Donc pour i et j, il y a n²/X²

Ce qui fait donc : n²/4 (sans le while)

Avec le while, comme n²/4 ne dépend plus de X, c'est facile, il suffit de multiplier par log_2 n

Soit une complexité en : n² log_2 n /4 en considérant que la représentation machine de n prend n bits.

Avec la représentation classique de |n| = log_2 n, alors la complexité serait en : O(exp(n²) n)