Types d'algorithmes

L'efficacité et la précision des algorithmes doivent être analysées pour les comparer et choisir un algorithme spécifique pour certains scénarios. Le processus de réalisation de cette analyse est appelé analyse asymptotique. Elle consiste à calculer le temps d'exécution de toute opération en unités mathématiques de calcul.

Par exemple, le temps d'exécution d'une opération est calculé comme f(n) et peut être pour une autre opération il est calculé comme g(n2). Cela signifie que le temps d'exécution de la première opération augmentera linéairement avec l'augmentation de n et que le temps d'exécution de la seconde opération augmentera exponentiellement lorsque n augmentera. De même, le temps d'exécution des deux opérations sera presque le même si n est significativement petit.

En général, le temps requis par un algorithme est de trois types :

• Meilleur cas : Temps minimum requis pour l'exécution du programme.
• Cas moyen : Temps moyen nécessaire à l'exécution du programme.
• Pire cas : Temps maximum nécessaire à l'exécution du programme.

Notations asymptotiques

Les notations asymptotiques couramment utilisées pour calculer la complexité du temps d'exécution d'un algorithme.

• Notation Ο
• Notation Ω
• Notation θ

Notation Big Oh, Ο