[Complexité d'un algorithme] Triangle de Sierpinski

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:

---

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

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

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

Citation:

---

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 ;)

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

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:

---

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

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

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 !

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 :oops:

merci

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

Citation:

---

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 8O ) mais je ne comprends paaaaass pourquoi ma solution est fausse :cry:

merci !

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:

---

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 ...

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:

---

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".

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)

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 :P

merci bien !

Pour moi, c'était autre chose :

Code:

---

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)

ben c'est ce que j'avais dit dans mon premier post :-)

la je crois qu'il parlait d'un autre exemple..

Citation:

---

Envoyé par jobherzt

ben c'est ce que j'avais dit dans mon premier post :-)

la je crois qu'il parlait d'un autre exemple..

---

oui, j'ai vu ça après :mrgreen: J'ai sauté le message et les autres avaient l'air de partir d'importe comment, donc j'avais voulu rectifier le tir :aie:

Je n'avais vu que ton deuxième post ou tu as du faire une erreur de frappe :

Citation:

---

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

---

Oups, oui je parlais d'un autre bout de code

Merci tout de même d'avoir refait le calcul :mrgreen: