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) :
Bon. Maintenant j'aimerais bien évaluer la complexité en fonction de n (en terme de grand O) de cet algorithme
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; }
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
Partager