^{PDFprof.com Search Engine}

CHAPITRE COMPLEXITÉ ET PREUVE D'ALGORITHME

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 prouver un algorithme ?
Pour prouver la validité d'un algorithme, il faut chercher un invariant de boucle, c'est-à-dire un prédicat de certaines variables de l'algorithme qui en font une proposition vraie à chaque entrée dans la boucle.
Quel est l'impact de la complexité d'un algorithme sur son efficacité ?
La complexité en temps sert à savoir quel algorithme il est préférable d'exécuter (sans prise en compte de la mémoire nécessaire) pour obtenir un résultat.
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée.
Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat.

Comment savoir la complexité d'un algorithme ?