Discussion :

[abdelhamidem]

Bonjour

Je fais un programme en Java sensé comparer differentes méthodes de calcul d'integral (rectangles, trapeze, simpson, monte carlo), et je voudrais ajouter une fonction qui compte grosso modo le nombre d'instruction effectuée par chacune des méthodes.

Habituellement les calculs de complexité sont basés sur les operations de comparaison et d'affectation. Mais dans le cas de mon programme, est ce qu'il ne faut pas prendre en compte les multiplications, divisions, addition etc... par exemple quand l'algorithme a besoin de calculer une valeur de f(x) en un certain point.

La fonction f(x) est donnée par l'utilisateur au debut du programme. On peut avoir une fonction dont les valeurs sont longues à calculer, comme on peut avoir f(x)=1.

Voila un bout de code pour vous donner une idée de ce à quoi ca ressemble:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
for (int i = 0; i < nbRectangles; i++) {
 
            eval = f(min + (max - min) * (2 * i + 1) / 200);
            resultat += (max - min) / nbRectangles * eval;
 
complexite =  complexite + ?????? ;
 
        }

[benDelphic]

la complexité d un algorithme est la somme de toutes les opérations ÉLÉMENTAIRES .
une opération élémentaire : affectation , comparaison, addition , soustraction, multiplication , division (meme ceux dans la boucle ).

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
for (int i = 0; i < nbRectangles; i++) {
 
            eval = f(min + (max - min) * (2 * i + 1) / 200);
            resultat += (max - min) / nbRectangles * eval;
 
        }
complexite =  complexite + i*(1 "comparaison"+ 3 " affectations"+4 "additions''+ 2 ''multiplications'' + 2 divisions+2 soustractions)+ 2 ;

[abdelhamidem]

ok, mais quand on ne sait pas de quoi va avoir l'air la fonction entrée par l'utilisateur... comment faire?

Si l'utilisateur entre f(x) = x... on sait qu'à chaque boucle, le calcul de la fonction ne demandera qu'une seule operation.

Par contre si c'est ln(cos(x^6-Pi)) ??

[benDelphic]

l' évaluation d 'une fonction étant un nombre constant d'opération tu peux prendre f(x) pour une opération élémentaire.

[abdelhamidem]

ah oui en effet, bonne idée...

Du coup, à la fin de la comparaison des algorithmes je pourrais dire que chacun a eu besoin de :

x + y*constante_f operations

en prenant constante_f ce nombre constant d'operations qu'il faut pour evaluer f