Discussion :

[Opérateur]

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]

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

[jobherzt]

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

[Opérateur]

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]

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]

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