Une introduction à la complexité temporelle des algorithmes

En informatique, l'analyse des algorithmes est une partie très cruciale. Il est important de trouver l'algorithme le plus efficace pour résoudre un problème. Il est possible d'avoir de nombreux algorithmes pour résoudre un problème, mais le défi ici est de choisir le plus efficace.

Maintenant, le point est, comment pouvons-nous reconnaître l'algorithme le plus efficace si nous avons un ensemble d'algorithmes différents? Ici, le concept de complexité spatiale et temporelle des algorithmes prend vie. La complexité spatiale et temporelle agit comme une échelle de mesure pour les algorithmes. Nous comparons les algorithmes sur la base de leur espace (quantité de mémoire) et de leur complexité temporelle (nombre d'opérations).

La quantité totale de mémoire de l'ordinateur utilisée par un algorithme lorsqu'il est exécuté est la complexité spatiale de cet algorithme. Nous ne discuterons pas de la complexité de l'espace dans cet article (pour rendre cet article un peu plus petit).

Complexité temporelle

Ainsi, la complexité temporelle est le nombre d'opérations qu'un algorithme effectue pour terminer sa tâche (étant donné que chaque opération prend le même temps). L'algorithme qui effectue la tâche dans le plus petit nombre d'opérations est considéré comme le plus efficace en termes de complexité temporelle. Cependant, la complexité spatiale et temporelle est également affectée par des facteurs tels que votre système d'exploitation et votre matériel, mais nous ne les incluons pas dans cette discussion.

Maintenant, pour comprendre la complexité temporelle, nous allons prendre un exemple dans lequel nous allons comparer deux algorithmes différents qui sont utilisés pour résoudre un problème particulier.

Le problème est la recherche. Nous devons rechercher un élément dans un tableau (dans ce problème, nous allons supposer que le tableau est trié par ordre croissant). Pour résoudre ce problème, nous avons deux algorithmes:

1. Recherche linéaire.

2. Recherche binaire.

Disons que le tableau contient dix éléments et que nous devons trouver le nombre dix dans le tableau.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

L' algorithme de recherche linéaire comparera chaque élément du tableau au search_digit . Lorsqu'il trouve le search_digit dans le tableau, il renvoie true .

Comptons maintenant le nombre d'opérations qu'il effectue. Ici, la réponse est 10 (puisqu'elle compare chaque élément du tableau). Ainsi, la recherche linéaire utilise dix opérations pour trouver l'élément donné (ce sont le nombre maximum d'opérations pour ce tableau; dans le cas de la recherche linéaire, cela est également connu comme le pire des cas d'un algorithme).

En général, la recherche linéaire prendra n nombre d'opérations dans son pire des cas (où n est la taille du tableau).

Examinons l' algorithme de recherche binaire pour ce cas.

La recherche binaire peut être facilement comprise par cet exemple:

Source: Learneroo

Si nous essayons d'appliquer cette logique à notre problème, nous allons d'abord comparer search_digit avec l'élément du milieu du tableau, c'est-à-dire 5. Maintenant que 5 est inférieur à 10, nous allons commencer à chercher le search_digit dans les éléments du tableau supérieur à 5, de la même manière jusqu'à ce que nous obtenions l'élément souhaité 10.

Maintenant, essayez de compter le nombre d'opérations de recherche binaire nécessaires pour trouver l'élément souhaité. Il a fallu environ quatre opérations. Maintenant, c'était le pire des cas pour la recherche binaire. Cela montre qu'il existe une relation logarithmique entre le nombre d'opérations effectuées et la taille totale du tableau.

nombre d'opérations = log (10) = 4 (environ)

pour la base 2

Nous pouvons généraliser ce résultat pour la recherche binaire comme:

Pour un tableau de taille n , le nombre d'opérations effectuées par la recherche binaire est: log (n)

La notation Big O

Dans les déclarations ci-dessus, nous avons vu que pour un tableau de taille n , la recherche linéaire effectuera n opérations pour terminer la recherche. D'autre part, la recherche binaire a effectué un nombre log (n) d'opérations (les deux pour leurs pires cas). Nous pouvons le représenter sous forme de graphique ( axe des x : nombre d'éléments, axe des y : nombre d'opérations).

Source: Techtud

Il ressort clairement de la figure que la vitesse à laquelle la complexité augmente pour la recherche linéaire est beaucoup plus rapide que celle pour la recherche binaire.

Lorsque nous analysons un algorithme, nous utilisons une notation pour représenter sa complexité temporelle et cette notation est la notation Big O.

Par exemple: la complexité temporelle pour la recherche linéaire peut être représentée par O (n) et O (log n) pour la recherche binaire (où n et log (n) sont le nombre d'opérations).

La complexité temporelle ou les notations Big O pour certains algorithmes populaires sont répertoriées ci-dessous:

  1. Recherche binaire: O (log n)
  2. Recherche linéaire: O (n)
  3. Tri rapide: O (n * log n)
  4. Tri de sélection: O (n * n)
  5. Vendeur itinérant: O (n!)

Conclusion

J'apprécie vraiment vos efforts si vous lisez toujours cet article. Maintenant, vous devez penser - pourquoi la complexité du temps est-elle si importante à comprendre?

Nous savons que pour un petit nombre d'éléments (disons 10), la différence entre le nombre d'opérations effectuées par recherche binaire et recherche linéaire n'est pas si grande. Mais dans le monde réel, la plupart du temps, nous traitons des problèmes comportant de gros morceaux de données.

Par exemple, si nous avons 4 milliards d'éléments à rechercher, alors, dans le pire des cas, la recherche linéaire prendra 4 milliards d'opérations pour accomplir sa tâche. La recherche binaire accomplira cette tâche en seulement 32 opérations. C'est une grosse différence. Supposons maintenant que si une opération prend 1 ms pour se terminer, la recherche binaire ne prendra que 32 ms alors que la recherche linéaire prendra 4 milliards de ms (soit environ 46 jours). C'est une différence significative.

C'est la raison pour laquelle l'étude de la complexité temporelle devient importante lorsqu'il s'agit d'une si grande quantité de données.

Ressources

Algorithmes de Grokking - par Aditya Y Bhargava

Introduction à la notation Big O et à la complexité temporelle - par CS Dojo