[Complexite] Tapis de Sierpinski, recursivite

Version imprimable

22/10/2005, 05h06
chateau_dur

[Complexite] Tapis de Sierpinski, recursivite

Salut,

J'ai code l'algo pour avoir un tapis de Sierpinski en recursif et j'aimerai savoir sa complexite, mais je vois pas trop comment faire sur un algo recursif. Comment on peut determiner le worst case ?

Si quelqu'un peut m'expliquer en 2 lignes c'est cool !

Merci d'avance !
22/10/2005, 13h17
Selenite

Il n'y a aucune complexité à calculer puisqu'il n'y a pas d'algorithme à proprement parler.
25/10/2005, 00h23
chateau_dur

Tu veux dire que l'algo n'est pas defini ? J'ai pas de condition d'arret a proprement parler ?

Mmmh certes mais je trouve ca bizarre qu'on puisse coder ca qd meme en fait :?
25/10/2005, 09h11
FrancisSourd

Les figures contiennent effectivement un nombre infini de trous en théorie. Si on les dessine à l'ordinateur, on ne se limite qu'à une profondeur finie dans la construction par récurrence.
A l'étape 0, il y a un trou blanc.
A l'étape 1: il faut rajouter 9 trous blancs.
A l'étape 2: 81 trous blancs.
A l'étape i: 9^i trous blancs.
On peut donc dire que l'algorithme pour tracer la figure à l'étape i est en O(1 + 9 + 9^2 + ... +9^i) c'est-à-dire en O(9^(i+1)).
25/10/2005, 12h00
Selenite

Citation:

Envoyé par FrancisSourd

Les figures contiennent effectivement un nombre infini de trous en théorie. Si on les dessine à l'ordinateur, on ne se limite qu'à une profondeur finie dans la construction par récurrence.
A l'étape 0, il y a un trou blanc.
A l'étape 1: il faut rajouter 9 trous blancs.
A l'étape 2: 81 trous blancs.
A l'étape i: 9^i trous blancs.
On peut donc dire que l'algorithme pour tracer la figure à l'étape i est en O(1 + 9 + 9^2 + ... +9^i) c'est-à-dire en O(9^(i+1)).

On évalue la complexité d'un algorithme en fonction d'une opération élémentaire.
Je prétend qu'il n'est pas pertinent d'évaluer la complexité en terme de trous blancs à ajouter ;-).
25/10/2005, 14h35
FrancisSourd

Citation:

Envoyé par Selenite

On évalue la complexité d'un algorithme en fonction d'une opération élémentaire.
Je prétend qu'il n'est pas pertinent d'évaluer la complexité en terme de trous blancs à ajouter ;-).

J'avais oublié de précisé que pour tracer un "trou", il faut un nombre constant d'opérations élémentaires (calcul des coordonnées, tracé des traits). La durée de l'algo est donc bien estimée par le nombre de trous.

On peut évidemment dire qu'un gros trou est plus long à tracer qu'un petit trou mais je n'ai jamais vu de telles considérations en géométrie algorithmique.
25/10/2005, 15h51
vdbadr

Salut tout le monde,

Citation:

A l'étape 0, il y a un trou blanc.
A l'étape 1: il faut rajouter 9 trous blancs.
A l'étape 2: 81 trous blancs.
A l'étape i: 9^i trous blancs.
On peut donc dire que l'algorithme pour tracer la figure à l'étape i est en O(1 + 9 + 9^2 + ... +9^i) c'est-à-dire en O(9^(i+1)).

Or, il se revele d'apres les dessins que c'est plutot :
NombreDeCotes^i pour l'étape i et non neuf pour toutes les formes géométiques sauf dans le cas d'une figure à 4 cotés (carré) pour lequel des trous sont rajoutés dans les coins

Je sais pas si ca vous avance ... :wink:

Wow, pas mal la discussion :D

Ceci dit, j'ai toujours du mal a voir et j'ai repense a la reponse de Selenite : "Il n'y a aucune complexité à calculer puisqu'il n'y a pas d'algorithme à proprement parler."

En effet car mon algo donne ca :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void DrawSierpinski(HDC hDC,int x1,int y1,int x2,int y2) { if(((x2-x1)/3)>1){ Rectangle(hDC,(2*x1+x2)/3,(2*y1+y2)/3,(x1+2*x2)/3, (y1+2*y2)/3); //Sleep(1); DrawSierpinski(hDC, (2*x1+x2)/3, y1, (x1+2*x2)/3, (2*y1+y2)/3); //up DrawSierpinski(hDC, (x1+2*x2)/3,y1,x2,(2*y1+y2)/3); //up right DrawSierpinski(hDC, (x1+2*x2)/3,(2 * y1 + y2) / 3.0,x2,(y1+2*y2)/3); //right DrawSierpinski(hDC, (x1+2*x2)/3,(y1+2*y2)/3,x2,y2); // down right DrawSierpinski(hDC, (2*x1+x2)/3, (y1+2*y2)/3,(x1 + 2*x2)/3.0,y2); //down DrawSierpinski(hDC, x1, (y1+2*y2) / 3.0, (2*x1+x2)/3,y2); //down left DrawSierpinski(hDC, x1, (2*y1+y2)/3,(2*x1+x2)/3, (y1+2*y2)/3); //left DrawSierpinski(hDC, x1, y1, (2*x1+x2)/3, (2*y1+y2)/3); //up left } }
Donc ma condition d'arret est completement arbitraire... en meme temps tout cela a qd meme un nombre d'operations que l'on peut evaluer...

Donc au final j'aime assez la reponse de Francis Sourd : O(1 + 9 + 9^2 + ... +9^i). Je vois pas vraiment ce que ca pourrais changer la complexite si on considerait le nombre de cote ?

Merci a tous en tout cas, mais si quelqu'un a une meilleure proposition je suis prenneur !

31/10/2005, 05h42
doccpu

je sait pas si ca t'avance mais les récursif sont tres mal digéré par les processeurs car sa créée des ressource en boucle et sa peu planter si c'est executé trop de fois (quelques milliards de milliards quand meme)

Citation:

Envoyé par chateau_dur

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void 
DrawSierpinski(HDC hDC,int x1,int y1,int x2,int y2)
{
	if(((x2-x1)/3)>1){	
 
		Rectangle(hDC,(2*x1+x2)/3,(2*y1+y2)/3,(x1+2*x2)/3, (y1+2*y2)/3);
		//Sleep(1);
 
		DrawSierpinski(hDC, (2*x1+x2)/3, y1, (x1+2*x2)/3, (2*y1+y2)/3); //up
        DrawSierpinski(hDC, (x1+2*x2)/3,y1,x2,(2*y1+y2)/3); //up right  
        DrawSierpinski(hDC, (x1+2*x2)/3,(2 * y1 + y2) / 3.0,x2,(y1+2*y2)/3); //right
        DrawSierpinski(hDC, (x1+2*x2)/3,(y1+2*y2)/3,x2,y2); // down right
        DrawSierpinski(hDC, (2*x1+x2)/3, (y1+2*y2)/3,(x1 + 2*x2)/3.0,y2); //down        
		DrawSierpinski(hDC, x1, (y1+2*y2) / 3.0, (2*x1+x2)/3,y2); //down left
		DrawSierpinski(hDC, x1, (2*y1+y2)/3,(2*x1+x2)/3, (y1+2*y2)/3); //left		
        DrawSierpinski(hDC, x1, y1, (2*x1+x2)/3, (2*y1+y2)/3); //up left
	}
}

Par contre la tu peux optimiser ton code en comptant d'abord avec ton récursif le nombre de trous et ensuite en les peignant avec une fonction externe en "for" ce qui me semble ira plus vite au niveau du prossesseur mais bon je peux me tromper !
genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
DrawSierpinski(HDC hDC, int intI)
{
int sierpinski = Sierpinski(intI);
for(int intX = 0; intX < sierpinski; intX++)
{
//traitement dessin
}
//traitement affichage
}
 
 
int Sierpinski(int intI)
{
// algo recursif de comptage genre
if (IntI = 0)
{
return 1;
}
else
{
return 9^intI + Sierpinski(intI-1);
}
}

31/10/2005, 16h27
chateau_dur

Ouais c'est vrai mais je voulais pas optimiser reelement, c'etait un exercice super scolaire, je joue le jeu, je le fais "straight forward" :D Mais merci en tout cas pour vos idees/conseils !