Complexité de l'algorithme et notation Big O

Discutons de la complexité des algorithmes, et en particulier de la façon dont nous la mesurons dans le contexte des algorithmes.

Différents algorithmes, ayant le même problème à résoudre et les mêmes entrées, prennent un temps différent pour résoudre le problème.

Parfois, un moment très différent, d'autant plus que le nombre d'éléments à gérer augmente.

Cette complexité s'appelleGrand O, pour aucune autre raison que nous n'utilisons une majusculeolettre comme convention:O(n),O(1)etc.

Les mesures les plus populaires de Big O que vous verrez, triées par plus efficace à moins efficace, sont:

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

nest le nombre d'entrées. Par exemple, si vous devez trier 2 élémentsnvaut 2, et si vous devez trier 20 000 éléments,nest 20.000.

Mais vous n'avez pas besoin de remplacer la valeur dans leO()calcul. C'est un symbole destiné à signaler aux développeurs et à tous ceux qui regardent les algorithmes son efficacité.

Un algorithme avecO(1)l'efficacité est la meilleure que nous puissions trouver. Le temps d'exécution ne dépend pas du nombre d'entrées, il faut toujours le même temps pour s'exécuter

Un algorithme avecO(n)Balancelinéairementavec le nombre d'entrées. Si avec 10 éléments, cela prend 1 seconde, avec 100 éléments, cela prendra 10 secondes.

Un algorithme avecO(n^2), si avec 4 éléments prend 16 secondes, avec 10 éléments prend 100 secondes.

Nous analyserons et calculerons l'efficacité Big O d'un bon nombre d'algorithmes dans les prochaines leçons.

Il est important de noter que la notation Big O ne nous donne pas toutes les informations dont nous avons besoin pour juger si un algorithme sera plus rapide qu'un autre, en particulier si leur valeur Big O est la même. Dans ce cas, vous devrez utiliser d'autres outils pour tester l'efficacité.

Mais lorsque les algorithmes ont des classes différentes (O(n)contreO(n^2)par exemple), cela ne fait aucun doute.