Complexité temporelle et spatiale

Une façon de mesurer l'efficacité d'un algorithme est la complexité temporelle (time complexity), une mesure formelle du temps qu'un algorithme nécessite pendant son exécution en fonction de la taille du problème. En plus de la complexité temporelle, les informaticiens s'intéressent également à la complexité spatiale (space complexity), la mesure formelle de la quantité de mémoire qu'un algorithme nécessite pendant son exécution en fonction de la taille du problème.

La complexité temporelle et spatiale sont toutes deux des mesures formelles de l'efficacité d'un algorithme (algorithm) en fonction de la taille du problème, en particulier lorsque nous travaillons avec de grandes quantités de données complexes. Par exemple, la gravité, le phénomène universel par lequel les choses s'attirent et se déplacent les unes vers les autres, peut être modélisée comme des forces qui agissent sur chaque paire d'objets dans l'univers. Simuler un sous-ensemble de l'univers qui ne contient que 100 corps astronomiques prendra beaucoup moins de temps qu'un univers beaucoup plus grand avec des milliards, des trillions, ou même plus de corps, qui gravitent tous les uns vers les autres. La taille du problème joue un rôle important dans la détermination du temps qu'un algorithme nécessite pour s'exécuter. Nous exprimerons souvent la taille du problème comme un nombre entier positif correspondant à la taille de l'ensemble de données, tel que le nombre de corps astronomiques dans notre simulation.

L'objectif de l'analyse de la complexité temporelle et spatiale est de produire une caractérisation simple et facile à comparer de l'efficacité d'un algorithme en fonction de la taille du problème. Considérez la description suivante d'un algorithme qui recherche un mot cible dans une liste. Commencez par le tout début de la liste et vérifiez si le premier mot est le mot cible. Si c'est le cas, nous avons trouvé le mot. Si ce n'est pas le cas, passez au mot suivant dans la liste et répétez le processus.

La première tâche consiste à identifier une métrique pour représenter la taille du problème. Généralement, l'analyse de la complexité temporelle suppose une analyse asymptotique (asymptotic analysis), se concentrant sur l'évaluation du temps qu'un algorithme prend pour produire un résultat à mesure que la taille de l'entrée augmente. Il y a deux entrées pour cet algorithme : (1) la liste de mots, et (2) le mot cible. La longueur moyenne d'un mot anglais est d'environ cinq caractères, de sorte que la taille du problème est principalement déterminée par le nombre de mots dans la liste plutôt que par la longueur d'un mot quelconque. (Cette hypothèse pourrait ne pas être juste si notre ensemble de données était plutôt une séquence d'ADN composée de millions de nucléotides – le temps nécessaire pour comparer une paire de longues séquences d'ADN pourrait être plus important que le nombre de séquences d'ADN comparées.) L'identification de la taille du problème est une première tâche importante car elle détermine les autres facteurs que nous pouvons considérer dans les tâches suivantes.

La tâche suivante consiste à modéliser le nombre d'étapes nécessaires à l'exécution de l'algorithme tout en considérant son comportement potentiel sur toutes les entrées possibles. Une étape (step) représente une opération de base dans l'ordinateur, comme la recherche d'une seule valeur, l'addition de deux valeurs ou la comparaison de deux valeurs. Comment le temps d'exécution (runtime) change-t-il à mesure que la taille du problème augmente ? Nous pouvons voir que la partie « répéter » de notre description est affectée par le nombre de mots dans la liste ; plus de mots peuvent potentiellement entraîner plus de répétitions.

Dans ce cas, nous choisissons un modèle de coût (cost model), qui est une caractérisation du temps d'exécution en termes d'opérations plus abstraites, telles que le nombre de répétitions (repetition). Plutôt que de compter des étapes individuelles, nous comptons plutôt les répétitions. Chaque répétition peut impliquer plusieurs recherches et comparaisons. En choisissant chaque répétition comme modèle de coût, nous déclarons que les quelques étapes nécessaires pour rechercher et comparer des éléments peuvent être effectivement traitées comme une seule opération pour simplifier notre analyse.

Cependant, cette analyse n'est pas tout à fait complète. Nous pourrions trouver le mot cible tôt dans la liste même si la liste est très grande. Bien que nous ayons défini la taille du problème comme le nombre de mots dans la liste, la taille du problème ne tient pas compte des mots exacts et de l'ordre des mots dans la liste. Les informaticiens disent que cet algorithme a un cas le plus favorable (best-case situation) lorsque le mot peut être trouvé au début de la liste, et une situation du pire cas (worst-case situation) lorsque le mot ne peut être trouvé qu'à la fin de la liste (ou, peut-être, pas du tout dans la liste). Une façon de tenir compte de la variation du temps d'exécution est l'analyse de cas (case analysis), qui est basée sur des facteurs autres que la taille du problème.

Enfin, nous pouvons formaliser notre description en utilisant soit un anglais précis, soit une notation mathématique spéciale appelée notation grand O (Big O notation), qui est le type de notation asymptotique le plus courant en informatique utilisé pour mesurer la complexité du pire cas. En anglais précis, nous pourrions dire que la complexité temporelle de cet algorithme de recherche séquentielle a deux cas (Figure 3.13) :

• Dans le cas le plus favorable (lorsque le mot cible est au début de la liste), la recherche séquentielle ne prend qu'une seule répétition pour trouver le mot dans la liste.
• Dans la situation du pire cas (lorsque le mot cible est soit à la fin de la liste, soit pas du tout dans la liste), la recherche séquentielle prend N répétitions où N est le nombre de mots dans la liste.

Figure 3.13 Le meilleur cas pour la recherche séquentielle dans une liste triée est de trouver le mot en haut de la liste, tandis que le pire cas est de trouver le mot en bas de la liste. (source: Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Bien que cette description capture toutes les idées nécessaires pour communiquer la complexité temporelle (time complexity), les informaticiens enrichiront généralement cette description de mathématiques pour transmettre une idée géométrique du temps d'exécution. L'ordre de grandeur (order of growth) est une prédiction géométrique de la complexité temporelle ou spatiale d'un algorithme en fonction de la taille du problème (Figure 3.14).

• Dans le meilleur cas, la recherche séquentielle a un ordre de grandeur constant (constant) qui ne prend pas plus de ressources à mesure que la taille du problème augmente.
• Dans le pire cas, la recherche séquentielle a un ordre de grandeur linéaire (linear) où les ressources nécessaires pour exécuter l'algorithme augmentent à peu près au même rythme que la taille du problème. Ceci est par rapport à N, le nombre de mots dans la liste.

Constant et linéaire sont deux exemples d'ordres de grandeur. Un algorithme (algorithm) avec un ordre de grandeur constant prend le même temps d'exécution même si la taille du problème devient de plus en plus grande – quelle que soit la taille du dictionnaire, il est possible de trouver le mot cible au tout début. En revanche, un algorithme avec une complexité temporelle linéaire prendra plus de temps à s'exécuter à mesure que la taille du problème augmente, et nous pouvons prédire qu'une augmentation de la taille du problème correspond à peu près à la même augmentation du temps d'exécution.

Cette prédiction est un résultat utile de l'analyse de la complexité temporelle. Elle nous permet d'estimer le temps d'exécution de l'algorithme de recherche séquentielle sur un problème de n'importe quelle taille, avant d'écrire le programme ou d'obtenir un dictionnaire de mots aussi grand. De plus, elle nous aide à décider si nous voulons utiliser cet algorithme ou explorer d'autres conceptions et approches d'algorithmes. Nous pourrions comparer cet algorithme de recherche séquentielle à l'algorithme de recherche binaire et ajuster notre conception d'algorithme en conséquence.

Figure 3.14 L'ordre de grandeur d'un algorithme est utile pour estimer son efficacité d'exécution à mesure que la taille de l'entrée augmente afin d'aider à déterminer l'approche algorithmique à adopter. (source: Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Notation grand O pour les ordres de grandeur

Dans les années 1970, les informaticiens ont appliqué la notation asymptotique (asymptotic notation), une notation mathématique qui définit formellement l'ordre de grandeur. Nous pouvons utiliser la notation grand O (Big O notation) pour décrire la complexité temporelle de l'algorithme de recherche séquentielle. En général, nous disons qu'une fonction f(N) est dans la classe de O(g(N)), notée f(N) = O(g(N)) ou f(N) dans O(g(N)), si lorsque N tend vers l'infini, le rapport f(N)/g(N) est borné supérieurement par une constante. La fonction g(N) est généralement une fonction simple qui définit l'ordre de grandeur, telle que g(N) = 1, g(N) = N (fonction linéaire), g(N) = log N, ou d'autres fonctions comme suit :

• Dans le meilleur cas, l'ordre de grandeur de la recherche séquentielle est en O(1).
• Dans le pire cas, l'ordre de grandeur de la recherche séquentielle est en O(N) par rapport à N, le nombre de mots dans la liste.

L'ordre de grandeur constant est décrit en notation grand O comme « O(1) » tandis que l'ordre de grandeur linéaire est décrit en notation grand O comme « O(N) par rapport à N, la taille du problème. » La notation grand O formalise le concept de prédiction. Étant donné la taille du problème, N, calculez le temps nécessaire pour exécuter l'algorithme sur un problème de cette taille. Pour les grandes listes, afin de doubler le temps d'exécution du pire cas de la recherche séquentielle, nous devrions doubler la taille de la liste.

O(1) et O(N) ne sont pas les seuls ordres de grandeur.

• O(1), ou constant.
• O(log N), ou logarithmique.
• O(N), ou linéaire.
• O(N log N), ou quasi-linéaire.
• O(N²), ou quadratique.
• O(N³), ou cubique.
• O(2^N), O(3^N), . . . , ou exponentiel.
• O(N!), ou factoriel.

L'ordre de grandeur O(log N), ou logarithmique, apparaît très souvent dans l'analyse d'algorithme. Le logarithme (logarithm) d'un grand nombre indique combien de fois il doit être divisé par un petit nombre jusqu'à ce qu'il atteigne 1. Le logarithme binaire (binary logarithm), ou log₂, indique combien de fois un grand nombre doit être divisé par 2 jusqu'à ce qu'il atteigne 1. Dans le pire cas, la complexité temporelle de la recherche séquentielle est en O(N) par rapport à N, le nombre de mots dans la liste, puisque chaque répétition de la recherche séquentielle élimine un élément restant. Qu'en est-il de la recherche binaire ? Dans le pire cas, la complexité temporelle de la recherche binaire est en O(log N) par rapport à N, le nombre de mots dans la liste, puisque chaque répétition de la recherche binaire élimine la moitié des éléments restants.

Une autre façon de comprendre les ordres de grandeur est de considérer comment un changement dans la taille du problème entraîne un changement dans l'utilisation des ressources. Lorsque nous doublons la taille du problème d'entrée, les algorithmes de chaque ordre de grandeur réagissent différemment (Figure 3.15).

• Les algorithmes en O(1) ne nécessiteront pas plus de ressources.
• Les algorithmes en O(log N) nécessiteront 1 unité de ressource supplémentaire.
• Les algorithmes en O(N) nécessiteront 2 fois le nombre de ressources.
• Les algorithmes en O(N log N) nécessiteront un peu plus de 2 fois le nombre de ressources.
• Les algorithmes en O(N²) nécessiteront 4 fois le nombre de ressources.
• Les algorithmes en O(N³) nécessiteront 8 fois le nombre de ressources.
• Les algorithmes en O(2^N), O(3^N), . . . nécessiteront le nombre de ressources au carré ou au cube.
• Les algorithmes en O(N!) nécessiteront encore plus.

Cette croissance se compose, de sorte que quadrupler la taille du problème pour un algorithme en O(N²) nécessitera 16 fois le nombre de ressources. La conception et la découverte d'algorithmes sont souvent motivées par ces différences massives entre les ordres de grandeur. Notez que cette explication de la façon dont chaque ordre de grandeur réagit différemment simplifie à l'excès le problème. Rigoureusement parlant, une fonction f(N) exprimée en notation grand O comme étant dans la classe de O(g(N)) peut être beaucoup plus complexe que la simple fonction g(N). Par exemple, f(N) = 4log N + 100 log(log N) est en O(log N), mais lorsque N double, f(2N) n'est certainement pas seulement une unité de plus que la fonction originale f(N). Un argument similaire s'applique à toutes les autres fonctions autres que la fonction constante O(1).

Figure 3.15 Ce tableau montre le temps qu'il faudrait à un algorithme avec chacun des ordres de grandeur donnés pour terminer son exécution sur un problème de la taille donnée, N. Lorsqu'un algorithme prend plus de 1025 ans à calculer, cela signifie qu'il prend plus de temps que l'âge actuel de l'univers. (source des données : Geeks for Geeks, « Big O Notation Tutorial—A Guide to Big O Analysis », dernière mise à jour le 29 mars 2024 ; source: Copyright Rice University, OpenStax, sous licence CC BY 4.0)

À mesure que la taille du problème augmente, la complexité algorithmique devient un facteur de plus en plus important. Pour les problèmes ne traitant que de 1 000 éléments, le temps qu'il faudrait pour exécuter un algorithme en temps exponentiel sur ce problème dépasse l'âge actuel de l'univers. En pratique, dans les applications travaillant avec de grandes quantités de données, O(N log N) est souvent considéré comme la limite pour les algorithmes du monde réel. Même dans ce cas, les algorithmes en O(N log N) ne peuvent pas être exécutés trop fréquemment. Pour les algorithmes qui doivent s'exécuter fréquemment sur de grandes quantités de données, les concepteurs d'algorithmes ciblent O(N), O(log N) ou O(1).