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