^{PDFprof.com Search Engine}

Exercice 1 : Complexité des algorithmes (8 points)

Comment savoir 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).
Quelle est l'ordre de grandeur de la complexité en temps de l'algorithme obtenu ?
Le coût (en temps) d'un algorithme ou complexité en temps est l'ordre de grandeur du nombre d'opérations arithmétiques ou logiques, du nombre d'accès en mémoire et d'affectation qu'on' doit effectuer lors de l'exécution d'un algorithme pour résoudre le problème auquel il est destiné.
Afin d'évaluer la complexité des différents algorithmes de tri présentés, on comptera le nombre de comparaisons et d'échanges de valeur entre deux éléments du tableau sans prendre en compte les affectations et comparaisons sur des variables de comptage de boucles.

Comment savoir la complexité d'un algorithme ?