+237 655 214 000   |   contact@itiss-group.com

Setup Menus in Admin Panel

1. Analyse de complexité

La complexité d’un algorithme est :

  • en temps, le nombre d’opérations élémentaires effectuées pour traiter une donnée de taille n ;
  • en mémoire, l’espace mémoire nécessaire pour traiter une donnée de taille n.

 

Elle permet d’exprimer l’efficacité d’un algorithme dans la résolution d’un problème, et par conséquent de comparer deux algorithmes.

 

Exemple :

Supposons que l’on dispose de deux ordinateurs. L’ordinateur A est capable d’effectuer 109 instructions par seconde. L’ordinateur B est capable d’effectuer 107 instructions par seconde. Considérons un même problème (de tri par exemple) dont la taille des données d’entrées est n. Pour l’ordinateur A, on utilise un algorithme qui réalise 2n2 instructions. Pour l’ordinateur B, on utilise un algorithme qui réalise 50nlog(n) instructions. Pour traiter une entrée de taille 106: l’ordinateur A prendra 2000s et l’ordinateur B prendra 100s. Ainsi même si la machine B est médiocre, elle résoudra le problème 20 fois plus vite que l’ordinateur A.

 

La complexité est exprimée en fonction du nombre de données et de leur taille. A défaut de pouvoir faire mieux :

  • On considère que les opérations sont toutes équivalentes
  • Seul l’ordre de grandeur nous intéresse.
  • On considère uniquement le pire des cas

 

Pour n données on aura comme exemples de complexités : O(n) linéaire, O(n2) quadratique O(n log(n)),…

 

SEE ALL Add a note
YOU
Add your Comment

Related Courses Widget

Course

top
© ITISS Edu. Tous droits réservés.
X