Discussion :

[chateau_dur]

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 !

[Selenite]

Il n'y a aucune complexité à calculer puisqu'il n'y a pas d'algorithme à proprement parler.

[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

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

[Selenite]

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

[FrancisSourd]

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.

[vdbadr]

Salut tout le monde,

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

[chateau_dur]

Wow, pas mal la discussion

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 :

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

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

[doccpu]

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

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

[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" Mais merci en tout cas pour vos idees/conseils !