Analyse des algorithmes
Premium
Complexité
Opération élémentaire
Coût unitaire
Coût en bits
Modèle de coût
Complexité temporelle
Temps constant
Analyse des algorithmes - Opérations élémentaires et modèles de coût
Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.