Salut
msedirim a écrit :
Pou évaluer la complexité théorique d'un algorithme, est ce que on utilise seulement les paramètres qui sont les entrées de l'algorithme ?
|
Qu'est ce que tu entends par ça ? Tu veux parler d'algorithmes avec effets de bord ?
msedirim a écrit :
Est ce que on peut trouver dans la valeur de la complexité des paramètres qui sont calculés dans l'algorithme ?
|
A priori je dirai non, mais je crois que je ne comprend pas bien ta question. (c'est quoi ce que tu appelles la complexité ? et c'est quoi ta définition d'un paramètre calculé ?)
Un outil très utilisé en algorithmique est l'ordre de l'algorithme. Il vise à déterminer le temps de calcul (en nombre d'opération) d'un algorithme en fonction de ses arguments. Pour déterminer l'ordre d'un algorithme, on construit à partir de son code le polynome de coût correspondant et on en prend le terme le plus élevé.
Par exemple, pour le code:
Code :
- int sum(int upBound) {
- int result = 0;
- for(int i = 1; i <= upBound; i++)
- result += i;
- }
|
On détermine la complexité en calculant le nombre d'itérations réalisées: il y en a upBound
Opérations = upBound
C'est un polynome de degrés 1, on dit qu'il est d'ordre O(x)
Maintenant, si je rajoute une boucle imbriquée,
Code :
- int sum2(int upBound) {
- int result = 0;
- for(int i = 1; i <= upBound; i++)
- for(int j = 1; j <= upBound; j++)
- result += i;
- }
|
On obtient un nombre d'opérations = upBound^2, on dit qu'il est d'ordre O(x^2)
A partir de ces deux fonctions, je peux calculer la complexité de l'algorithme qui consiste à exécuter sum suivi de sum2; le nombre d'opération effecté est la somme du nombre d'opérations effectuées dans chaque fonction = upBound + upBound^2
La complexité est alors d'ordre O(x^2). On écarte le terme en O(x) car il est négligeable devant le terme en O(x^2) lorsque x tend vers l'infini.
Enfin, je peux directement déduire de ces valeurs la complexité du calcul sum(sum2(upBound)), c'est le produit des complexités des deux algorithmes:
Le nombre d'opérations = upBound * upBound^2 = upBound^3
On a donc un algorithme d'ordre O(x^3)
C'est une méthode qui donne un bon aperçu de la performance d'un algorithme pour des valeurs infinies.
En effet, si tu prends des valeurs de taille finie, il sera sans doutes préférable d'avoir un algorithme effectuant x + 0.00001x^5 opérations (ordre O(x^5)) qu'un algorithme "optimisé" effectuant x^2 opérations (ordre O(x^2) ) car le terme en x^5 sera négligeable par rapport au terme en x.
