Bonjour,
 
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 ?
 
Est ce que on peut trouver dans la valeur de la complexité des paramètres qui sont calculés dans l'algorithme ?
 
En général, comment on évalue la complexité théorique d'un algorithme?
 
Merci.

Salut
 

 
Qu'est ce que tu entends par ça ? Tu veux parler d'algorithmes avec effets de bord ?
 

 
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:

 
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,  

 
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.

j'ai un peu les yeux qui saignent ...
 
http://www.enseignement.polytechni [...] index.html

 
Je vois pas trop en quoi ca diffère de ce que j'ai dis  

 
j'ai répondu avant de voir ta réponse, c'ets l'OP qui me faisait saigner des yeux