Analyse d'algorithmes - Analysis of algorithms

Pour rechercher une entrée donnée dans une liste ordonnée donnée, l' algorithme de recherche binaire et linéaire (qui ignore l'ordre) peut être utilisé. L'analyse du premier et du dernier algorithme montre qu'il faut au plus log 2 ( n ) et n étapes de contrôle, respectivement, pour une liste de longueur n . Dans la liste d'exemples illustrée de longueur 33, la recherche de "Morin, Arthur" prend 5 et 28 étapes avec une recherche binaire (affichée en cyan ) et linéaire ( magenta ), respectivement.
Graphiques des fonctions couramment utilisées dans l'analyse des algorithmes, montrant le nombre d'opérations N par rapport à la taille d'entrée n pour chaque fonction

En informatique , l' analyse des algorithmes est le processus consistant à trouver la complexité de calcul des algorithmes - la quantité de temps, de stockage ou d'autres ressources nécessaires pour les exécuter . Habituellement, cela implique de déterminer une fonction qui relie la longueur de l'entrée d'un algorithme au nombre d'étapes qu'il prend (sa complexité temporelle ) ou au nombre d'emplacements de stockage qu'il utilise (sa complexité spatiale ). Un algorithme est dit efficace lorsque les valeurs de cette fonction sont petites ou croissent lentement par rapport à une croissance de la taille de l'entrée. Différentes entrées de la même longueur peuvent entraîner un comportement différent de l'algorithme, de sorte que les descriptions du meilleur, du pire et du moyen peuvent toutes être d'un intérêt pratique. Sauf indication contraire, la fonction décrivant les performances d'un algorithme est généralement une limite supérieure , déterminée à partir des entrées les plus défavorables de l'algorithme.

Le terme « analyse d'algorithmes » a été inventé par Donald Knuth . L'analyse d'algorithmes est une partie importante d'une théorie plus large de la complexité de calcul , qui fournit des estimations théoriques des ressources nécessaires à tout algorithme qui résout un problème de calcul donné . Ces estimations donnent un aperçu des directions raisonnables de recherche d' algorithmes efficaces .

Dans l'analyse théorique des algorithmes, il est courant d'estimer leur complexité au sens asymptotique, c'est-à-dire d'estimer la fonction de complexité pour une entrée arbitrairement grande. Notation Big O , Big-Omega notation et Big-theta notation sont utilisés à cette fin. Par exemple, on dit que la recherche binaire s'exécute en un nombre d'étapes proportionnelles au logarithme de la longueur de la liste triée recherchée, ou en O(log(n)), familièrement "en temps logarithmique ". Habituellement, des estimations asymptotiques sont utilisées car différentes implémentations du même algorithme peuvent différer en efficacité. Cependant, les efficacités de deux implémentations "raisonnables" d'un algorithme donné sont liées par un facteur multiplicatif constant appelé constante cachée .

Des mesures exactes (non asymptotiques) d'efficacité peuvent parfois être calculées mais elles nécessitent généralement certaines hypothèses concernant la mise en œuvre particulière de l'algorithme, appelée modèle de calcul . Un modèle de calcul peut être défini en termes d'un ordinateur abstrait , par exemple, une machine de Turing , et/ou en postulant que certaines opérations sont exécutées en unité de temps. Par exemple, si la liste triée à laquelle nous appliquons la recherche binaire a n éléments, et nous pouvons garantir que chaque recherche d'un élément dans la liste peut être effectuée en unité de temps, alors au plus log 2 n + 1 unités de temps sont nécessaires pour retourner une réponse.

Modèles de coûts

Les estimations d'efficacité temporelle dépendent de ce que nous définissons comme une étape. Pour que l'analyse corresponde utilement au temps d'exécution réel, il faut garantir que le temps nécessaire à l'exécution d'une étape soit borné au-dessus par une constante. Il faut être prudent ici ; par exemple, certaines analyses comptent une addition de deux nombres comme une étape. Cette hypothèse peut ne pas être justifiée dans certains contextes. Par exemple, si les nombres impliqués dans un calcul peuvent être arbitrairement grands, le temps requis par une seule addition ne peut plus être supposé constant.

Deux modèles de coûts sont généralement utilisés :

  • le modèle de coût uniforme , également appelé mesure de coût uniforme (et variations similaires), attribue un coût constant à chaque opération de la machine, quelle que soit la taille des nombres impliqués
  • le modèle de coût logarithmique , également appelé mesure de coût logarithmique (et variations similaires), attribue un coût à chaque opération de la machine proportionnel au nombre de bits impliqués

Ce dernier est plus lourd à utiliser, il n'est donc utilisé que lorsque cela est nécessaire, par exemple dans l'analyse d' algorithmes arithmétiques à précision arbitraire , comme ceux utilisés en cryptographie .

Un point clé qui est souvent négligé est que les limites inférieures publiées pour les problèmes sont souvent données pour un modèle de calcul qui est plus restreint que l'ensemble d'opérations que vous pourriez utiliser dans la pratique et donc il existe des algorithmes qui sont plus rapides que ce qui serait naïvement pensé possible.

Analyse du temps d'exécution

L'analyse du temps d' exécution est une classification théorique qui estime et anticipe l'augmentation du temps d'exécution (ou temps d'exécution) d'un algorithme à mesure que sa taille d'entrée (généralement notée n ) augmente. L'efficacité à l'exécution est un sujet de grand intérêt en informatique : un programme peut prendre des secondes, des heures, voire des années pour terminer son exécution, selon l'algorithme qu'il implémente. Alors que les techniques de profilage logiciel peuvent être utilisées pour mesurer le temps d'exécution d'un algorithme dans la pratique, elles ne peuvent pas fournir de données de synchronisation pour toutes les entrées possibles infiniment nombreuses ; ce dernier ne peut être atteint que par les méthodes théoriques d'analyse à l'exécution.

Lacunes des métriques empiriques

Étant donné que les algorithmes sont indépendants de la plate-forme (c'est -à- dire qu'un algorithme donné peut être implémenté dans un langage de programmation arbitraire sur un ordinateur arbitraire exécutant un système d'exploitation arbitraire ), il y a d'autres inconvénients importants à utiliser une approche empirique pour évaluer les performances comparatives d'un ensemble donné de algorithmes.

Prenons comme exemple un programme qui recherche une entrée spécifique dans une liste triée de taille n . Supposons que ce programme soit implémenté sur l'ordinateur A, une machine à la pointe de la technologie, utilisant un algorithme de recherche linéaire , et sur l'ordinateur B, une machine beaucoup plus lente, utilisant un algorithme de recherche binaire . Les tests de référence sur les deux ordinateurs exécutant leurs programmes respectifs peuvent ressembler à ceci :

n (taille de la liste) Temps d'exécution de l'ordinateur A
(en nanosecondes )
Temps d'exécution de l'ordinateur B
(en nanosecondes )
16 8 100 000
63 32 150 000
250 125 200 000
1 000 500 250 000

Sur la base de ces mesures, il serait facile de conclure que l' ordinateur A exécute un algorithme dont l'efficacité est de loin supérieure à celle de l' ordinateur B . Cependant, si la taille de la liste d'entrée est augmentée jusqu'à un nombre suffisant, il est clairement démontré que cette conclusion est erronée :

n (taille de la liste) Temps d'exécution de l'ordinateur A
(en nanosecondes )
Temps d'exécution de l'ordinateur B
(en nanosecondes )
16 8 100 000
63 32 150 000
250 125 200 000
1 000 500 250 000
... ... ...
1 000 000 500 000 500 000
4 000 000 2 000 000 550 000
16 000 000 8 000 000 600 000
... ... ...
63 072 × 10 12 31 536 × 10 12 ns,
soit 1 an
1 375 000 ns,
ou 1,375 millisecondes

L'ordinateur A, exécutant le programme de recherche linéaire, présente un taux de croissance linéaire . Le temps d'exécution du programme est directement proportionnel à sa taille d'entrée. Doubler la taille d'entrée double le temps d'exécution, quadrupler la taille d'entrée quadruple le temps d'exécution, et ainsi de suite. D'autre part, l'ordinateur B, exécutant le programme de recherche binaire, présente un taux de croissance logarithmique . Le quadruplement de la taille d'entrée n'augmente le temps d'exécution que d'une quantité constante (dans cet exemple, 50 000 ns). Même si l'ordinateur A est apparemment une machine plus rapide, l'ordinateur B dépassera inévitablement l'ordinateur A en temps d'exécution car il exécute un algorithme avec un taux de croissance beaucoup plus lent.

Ordres de croissance

De manière informelle, on peut dire qu'un algorithme présente un taux de croissance de l'ordre d'une fonction mathématique si au-delà d'une certaine taille d'entrée n , la fonction multipliée par une constante positive fournit une limite supérieure ou une limite pour le temps d'exécution de cet algorithme. En d'autres termes, pour une taille d'entrée donnée n supérieure à un certain n 0 et une constante c , le temps d'exécution de cet algorithme ne sera jamais supérieur à . Ce concept est fréquemment exprimé en utilisant la notation Big O. Par exemple, étant donné que le temps d'exécution du tri par insertion croît de manière quadratique à mesure que sa taille d'entrée augmente, on peut dire que le tri par insertion est d'ordre O ( n 2 ).

La notation Big O est un moyen pratique d'exprimer le pire des cas pour un algorithme donné, bien qu'elle puisse également être utilisée pour exprimer le cas moyen - par exemple, le pire des cas pour le tri rapide est O ( n 2 ), mais le temps d'exécution du cas moyen est O ( n  log  n ) .

Ordres empiriques de croissance

En supposant que le temps d'exécution suit la règle de puissance, t kn a , le coefficient a peut être trouvé en prenant des mesures empiriques du temps d'exécution à certains points de la taille du problème , et en calculant de telle sorte que . En d'autres termes, cela mesure la pente de la ligne empirique sur le graphique log–log du temps d'exécution en fonction de la taille du problème, à un certain point de taille. Si l'ordre de croissance suit en effet la règle de puissance (et donc la ligne sur le tracé log–log est bien une ligne droite), la valeur empirique de a restera constante à différentes plages, et sinon, elle changera (et la ligne est une ligne courbe) - mais pourrait toujours servir à la comparaison de deux algorithmes donnés quant à leurs ordres locaux empiriques de comportement de croissance . Appliqué au tableau ci-dessus :

n (taille de la liste) Temps d'exécution de l'ordinateur A
(en nanosecondes )
Ordre de croissance local
(n^_)
Temps d'exécution de l'ordinateur B
(en nanosecondes )
Ordre de croissance local
(n^_)
15 7 100 000
65 32 1.04 150 000 0,28
250 125 1.01 200 000 0,21
1 000 500 1,00 250 000 0,16
... ... ...
1 000 000 500 000 1,00 500 000 0,10
4 000 000 2 000 000 1,00 550 000 0,07
16 000 000 8 000 000 1,00 600 000 0,06
... ... ...

On voit clairement que le premier algorithme présente un ordre de croissance linéaire suivant en effet la règle de puissance. Les valeurs empiriques de la seconde diminuent rapidement, ce qui suggère qu'elle suit une autre règle de croissance et qu'elle a en tout cas des ordres de croissance locaux beaucoup plus faibles (et s'améliorant encore plus), empiriquement, que la première.

Évaluation de la complexité d'exécution

La complexité d'exécution pour le pire des cas d'un algorithme donné peut parfois être évaluée en examinant la structure de l'algorithme et en faisant quelques hypothèses simplificatrices. Considérez le pseudo - code suivant :

1    get a positive integer n from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

Un ordinateur donné prendra un temps discret pour exécuter chacune des instructions impliquées dans l'exécution de cet algorithme. Le temps spécifique pour exécuter une instruction donnée variera en fonction de l'instruction en cours d'exécution et de l'ordinateur qui l'exécute, mais sur un ordinateur conventionnel, ce temps sera déterministe . Disons que les actions effectuées à l'étape 1 sont considérées comme consommant le temps T 1 , l'étape 2 utilise le temps T 2 , et ainsi de suite.

Dans l'algorithme ci-dessus, les étapes 1, 2 et 7 ne seront exécutées qu'une seule fois. Pour une évaluation dans le pire des cas, il faut supposer que l'étape 3 sera également exécutée. Ainsi, le temps total pour exécuter les étapes 1 à 3 et l'étape 7 est :

Les boucles des étapes 4, 5 et 6 sont plus délicates à évaluer. Le test de boucle externe de l'étape 4 s'exécutera ( n + 1 ) fois (notez qu'une étape supplémentaire est nécessaire pour terminer la boucle for, donc n + 1 et non n exécutions), ce qui consommera du temps T 4 ( n + 1 ) . La boucle interne, d'autre part, est régie par la valeur de j, qui itère de 1 à i . Lors du premier passage dans la boucle externe, j itère de 1 à 1 : la boucle interne fait un passage, donc l'exécution du corps de la boucle interne (étape 6) consomme T 6 fois, et le test de la boucle interne (étape 5) consomme 2 T 5 fois. Lors du prochain passage dans la boucle externe, j itère de 1 à 2 : la boucle interne effectue deux passages, donc l'exécution du corps de la boucle interne (étape 6) consomme 2 T 6 temps, et le test de la boucle interne (étape 5) consomme 3 T 5 fois.

Au total, le temps total requis pour exécuter le corps de la boucle interne peut être exprimé sous forme de progression arithmétique :

qui peut être pris en compte comme

Le temps total requis pour exécuter le test de boucle externe peut être évalué de la même manière :

qui peut être pris en compte comme

Par conséquent, le temps d'exécution total de cet algorithme est :

qui se réduit à

En règle générale , on peut supposer que le terme d'ordre le plus élevé dans une fonction donnée domine son taux de croissance et définit ainsi son ordre d'exécution. Dans cet exemple, n 2 est le terme d'ordre le plus élevé, on peut donc conclure que f(n) = O(n 2 ). Formellement, cela peut être prouvé comme suit :

Prouve-le





Soit k une constante supérieure ou égale à [ T 1 .. T 7 ] Donc



Une approche plus élégante pour analyser cet algorithme serait de déclarer que [ T 1 .. T 7 ] sont tous égaux à une unité de temps, dans un système d'unités choisi de telle sorte qu'une unité soit supérieure ou égale aux temps réels pour ces étapes. Cela signifierait que le temps d'exécution de l'algorithme se décompose comme suit :

Analyse du taux de croissance des autres ressources

La méthodologie de l'analyse à l'exécution peut également être utilisée pour prédire d'autres taux de croissance, tels que la consommation d' espace mémoire . À titre d'exemple, considérons le pseudocode suivant qui gère et réaffecte l'utilisation de la mémoire par un programme en fonction de la taille d'un fichier que ce programme gère :

while file is still open:
    let n = size of file
    for every 100,000 kilobytes of increase in file size
        double the amount of memory reserved

Dans ce cas, à mesure que la taille du fichier n augmente, la mémoire sera consommée à un taux de croissance exponentiel , qui est d'ordre O(2 n ). Il s'agit d'un taux de croissance extrêmement rapide et probablement ingérable de la consommation de ressources mémoire .

Pertinence

L'analyse d'algorithme est importante dans la pratique car l'utilisation accidentelle ou non intentionnelle d'un algorithme inefficace peut avoir un impact significatif sur les performances du système. Dans les applications sensibles au temps, un algorithme prenant trop de temps à exécuter peut rendre ses résultats obsolètes ou inutiles. Un algorithme inefficace peut également finir par nécessiter une quantité non économique de puissance de calcul ou de stockage pour s'exécuter, le rendant à nouveau pratiquement inutile.

Facteurs constants

L'analyse des algorithmes se concentre généralement sur les performances asymptotiques, en particulier au niveau élémentaire, mais dans les applications pratiques, les facteurs constants sont importants et les données du monde réel sont en pratique toujours de taille limitée. La limite est généralement la taille de la mémoire adressable, donc sur les machines 32 bits 2 32 = 4 Gio (plus si la mémoire segmentée est utilisée) et sur les machines 64 bits 2 64 = 16 EiB. Ainsi étant donné une taille limitée, un ordre de croissance (temps ou espace) peut être remplacé par un facteur constant, et en ce sens tous les algorithmes pratiques sont O(1) pour une constante assez grande, ou pour des données assez petites.

Cette interprétation est surtout utile pour les fonctions dont la croissance est extrêmement lente : le logarithme (binaire) itéré (log * ) est inférieur à 5 pour toutes les données pratiques (2 65536 bits) ; (binaire) log-log (log log n ) est inférieur à 6 pour pratiquement toutes les données pratiques (2 64 bits); et le log binaire (log n ) est inférieur à 64 pour pratiquement toutes les données pratiques (2 64 bits). Un algorithme à complexité non constante peut néanmoins être plus efficace qu'un algorithme à complexité constante sur des données pratiques si la surcharge de l'algorithme à temps constant entraîne un facteur constant plus grand, par exemple, on peut avoir tant que et .

Pour les grandes données, les facteurs linéaires ou quadratiques ne peuvent pas être ignorés, mais pour les petites données, un algorithme asymptotiquement inefficace peut être plus efficace. Ceci est particulièrement utilisé dans les algorithmes hybrides , comme Timsort , qui utilisent un algorithme asymptotiquement efficace (ici merge sort , avec une complexité temporelle ), mais passent à un algorithme asymptotiquement inefficace (ici insertion sort , avec une complexité temporelle ) pour les petites données, comme le plus simple l'algorithme est plus rapide sur les petites données.

Voir également

Remarques

Les références

Liens externes