^{PDFprof.com Search Engine}

Leçon 926 : Analyse des algorithmes : Complexité Exemples

Comment évaluer la complexité d'un algorithme ?
La complexité en temps d'un algorithme sera exprimé par une fonction, notée T (pour Time), qui dépend : de la taille des données passées en paramètres : plus ces données seront volumineuses, plus il faudra d'opérations élémentaires pour les traiter.
On notera n le nombre de données à traiter.
Comment calculer la complexité d'une boucle while ?
Calcul de la complexité temporelle :
On effectue : 1 comparaison avec au plus : • 1 affectation, • une boucle while de longueur au plus p avec, à chaque itération, 2 comparaisons et 1 addition, 1 comparaison avec, dans tous les cas, 1 renvoi.
Le nombre total d'opérations est donc : 1+3p +2 = O(p).
Qu'est-ce qu'un algorithme complexe ?
La complexité d'un algorithme est une mesure du temps[1] requis par l'algorithme pour accomplir sa tâche, en fonction de la taille[2] de l'échantillon à traiter.
On dira d'un problème qu'il est aussi complexe que le meilleur algorithme connu pour le résoudre.
La complexité d'un algorithme est une mesure de la quantité de temps et/ou d'espace requise par un algorithme.
La complexité temporelle est le temps nécessaire à l'exécution d'un algorithme, en fonction de la longueur des données en entrée.

Comment évaluer la complexité d'un algorithme ?