Ingoré par de nombreux développeur. Big O reste une notion très importante. Si vous avez suivi des cours liés aux algorithmes? Si vous n’avez pas entendu parler de Big O, dans cet article je vous apprends comment maîtriser Big O en 10 minutes.
Qu’est que la notion de Big O ?
Dans cet article, nous aurons une discussion approfondie sur la notation Big O. Nous allons commencer par un exemple d’algorithme pour vous faire comprendre facilement. Ensuite, nous entrerons un peu dans les mathématiques pour avoir une compréhension plus détaillé. Après cela, nous passerons en revue quelques variantes courantes de la notation Big O. En fin de compte, nous discuterons de certaines des limites de Big O dans un scénario pratique. Une table des matières se trouve ci-dessous.
1. Qu’est-ce que la notation Big O et pourquoi est-ce important
Pour faire simple la notation Big O décrit la complexité de votre code en utilisant des termes algébriques.
Pour comprendre ce qu’est la notation Big O, nous pouvons jeter un oeil à un exemple typique, O(n²), qui se prononce généralement « Big O au carré». La lettre « n » représente ici la taille d’entrée, et la fonction « g(n) = n² » à l’intérieur du « O() » nous donne une idée de la complexité de l’algorithme par rapport à la taille d’entrée.
Un algorithme typique qui a la complexité de O(n²) serait l’algorithme de tri par sélection. Le tri par sélection est un algorithme de tri qui parcourt la liste pour s’assurer que chaque élément à l’index i est le ième élément le plus petit/le plus grand de la liste.