Notation Big O expliquée avec des exemples

La notation Big O est un moyen de décrire la vitesse ou la complexité d'un algorithme donné. Si votre projet actuel nécessite un algorithme prédéfini, il est important de comprendre sa vitesse ou sa lenteur par rapport aux autres options.

Qu'est-ce que la notation Big O et comment ça marche?

En termes simples, la notation Big O vous indique le nombre d'opérations qu'un algorithme effectuera. Il tire son nom du littéral "Big O" devant le nombre estimé d'opérations.

Ce que la notation Big O ne vous dit pas, c'est la vitesse de l'algorithme en secondes. Il y a beaucoup trop de facteurs qui influencent le temps d'exécution d'un algorithme. Au lieu de cela, vous utiliserez la notation Big O pour comparer différents algorithmes en fonction du nombre d'opérations qu'ils effectuent.

Big O établit un temps d'exécution dans le pire des cas

Imaginez que vous êtes enseignant avec une élève nommée Jane. Vous voulez trouver ses dossiers, vous utilisez donc un algorithme de recherche simple pour parcourir la base de données de votre district scolaire.

Vous savez qu'une recherche simple prend O (n) fois pour s'exécuter. Cela signifie que, dans le pire des cas, vous devrez rechercher dans chaque enregistrement (représenté par n) pour trouver celui de Jane.

Mais lorsque vous exécutez la recherche simple, vous constatez que les enregistrements de Jane sont la toute première entrée de la base de données. Vous n'êtes pas obligé de regarder toutes les entrées - vous les avez trouvées lors de votre premier essai.

Cet algorithme a-t-il pris O (n) temps? Ou a-t-il fallu du temps à O (1) parce que vous avez trouvé les disques de Jane du premier coup?

Dans ce cas, 0 (1) est le meilleur des cas - vous avez eu de la chance que les records de Jane soient au sommet. Mais la notation Big O se concentre sur le pire des cas, qui est 0 (n) pour une recherche simple. C'est une assurance que la recherche simple ne sera jamais plus lente que O (n) temps.

Les temps d'exécution des algorithmes augmentent à des rythmes différents

Supposons qu'il faut 1 milliseconde pour vérifier chaque élément de la base de données du district scolaire.

Avec une recherche simple, si vous devez vérifier 10 entrées, il faudra 10 ms pour s'exécuter. Mais avec l' algorithme de recherche binaire , vous n'avez qu'à vérifier 3 éléments, ce qui prend 3 ms pour s'exécuter.

Dans la plupart des cas, la liste ou la base de données que vous devez rechercher contiendra des centaines ou des milliers d'éléments.

S'il y a 1 milliard d'éléments, l'utilisation d'une recherche simple prendra jusqu'à 1 milliard de ms, soit 11 jours. D'un autre côté, l'utilisation de la recherche binaire ne prendra que 32 ms dans le pire des cas:

Il est clair que les temps d'exécution de la recherche simple et de la recherche binaire n'augmentent pas à peu près au même rythme. Au fur et à mesure que la liste des entrées s'agrandit, la recherche binaire prend un peu plus de temps à s'exécuter. Le temps d'exécution de la recherche simple augmente de façon exponentielle à mesure que la liste des entrées augmente.

C'est pourquoi il est si important de savoir comment le temps d'exécution augmente par rapport à la taille d'une liste. Et c'est exactement là que la notation Big O est si utile.

La notation Big O indique le nombre d'opérations

Comme mentionné ci-dessus, la notation Big O n'indique pas l' heure à laquelle un algorithme s'exécutera. Au lieu de cela, il affiche le nombre d'opérations qu'il effectuera. Il vous indique la vitesse de croissance d'un algorithme et vous permet de le comparer avec d'autres.

Voici quelques algorithmes courants et leurs temps d'exécution en notation Big O:

Notation Big OExemple d'algorithme
O (log n)Recherche binaire
Sur)Recherche simple
O (n * log n)Tri rapide
O (n2)Tri de sélection
Sur!)Vendeur itinérant

Maintenant, vous en savez assez pour être dangereux avec la notation Big O. Sortez et commencez à comparer des algorithmes.