Estimation de la complexité informatique. Évaluer la complexité des algorithmes, ou Qu'est-ce que O(log n). Il arrive souvent que le temps d'exécution d'un même algorithme, outre la taille du problème, soit influencé par d'autres paramètres saisis par l'utilisateur.

Il est important pour tout programmeur de connaître les bases de la théorie des algorithmes, puisque c'est cette science qui étudie les caractéristiques générales des algorithmes et les modèles formels de leur représentation. Depuis les cours d'informatique, on nous apprend à créer des organigrammes, ce qui permet ensuite de rédiger des problèmes plus complexes qu'à l'école. Ce n'est pas non plus un secret qu'il existe presque toujours plusieurs façons de résoudre un problème particulier : certaines impliquent de consacrer beaucoup de temps, d'autres des ressources, et d'autres encore n'aident qu'à trouver approximativement une solution.

Vous devez toujours rechercher l'optimum en fonction de la tâche, en particulier lors du développement d'algorithmes pour résoudre une classe de problèmes.
Il est également important d'évaluer comment l'algorithme se comportera avec des valeurs initiales de différents volumes et quantités, de quelles ressources il aura besoin et combien de temps il faudra pour obtenir le résultat final.
C’est le sujet d’une branche de la théorie des algorithmes – la théorie de l’analyse asymptotique des algorithmes.

Dans cet article, je propose de décrire les principaux critères d'évaluation et de donner un exemple d'évaluation d'un algorithme simple. Habrahabr dispose déjà d'informations sur les méthodes d'évaluation des algorithmes, mais elles s'adressent principalement aux étudiants du lycée. Cette publication peut être considérée comme une extension de cet article.

Définitions

Le principal indicateur de la complexité de l'algorithme est le temps nécessaire pour résoudre le problème et la quantité de mémoire requise.
De plus, lors de l'analyse de la complexité d'une classe de problèmes, un certain nombre est déterminé qui caractérise une certaine quantité de données - taille de l'entrée.
On peut donc conclure que complexité de l'algorithme est fonction de la taille de l’entrée.
La complexité de l'algorithme peut être différente pour la même taille d'entrée, mais des données d'entrée différentes.

Il existe des concepts de complexité dans le pire, moyenne ou le meilleur cas de scenario. Habituellement, la complexité est estimée dans le pire des cas.

Complexité temporelle dans le pire des cas, elle est fonction de la taille d'entrée, égale au nombre maximum d'opérations effectuées lors du fonctionnement de l'algorithme lors de la résolution d'un problème d'une taille donnée.
Complexité capacitive dans le pire des cas, une fonction de la taille d'entrée égale au nombre maximum de cellules mémoire consultées lors de la résolution de problèmes d'une taille donnée.

Ordre de complexité croissante des algorithmes

Ordre de difficulté croissant(ou complexité axiomatique) décrit le comportement approximatif de la fonction de complexité de l'algorithme lorsque la taille d'entrée est grande. Il s'ensuit que lors de l'estimation de la complexité temporelle, il n'est pas nécessaire de considérer les opérations élémentaires, il suffit de considérer les étapes de l'algorithme.

Étape de l'algorithme– un ensemble d'opérations élémentaires disposées séquentiellement, dont le temps d'exécution ne dépend pas de la taille de l'entrée, c'est-à-dire qu'il est limité d'en haut par une certaine constante.

Types d'estimations asymptotiques

O – pire estimation du cas

Considérez la complexité f(n) > 0, une fonction du même ordre g(n) > 0, taille de l'entrée n > 0.
Si f(n) = O(g(n)) et il y a des constantes c > 0, n 0 > 0, Que
0 < f(n) < c*g(n),
Pour n > n 0.

La fonction g(n) dans ce cas est une estimation asymptotiquement exacte de f(n). Si f(n) est fonction de la complexité de l'algorithme, alors l'ordre de complexité est défini comme f(n) – O(g(n)).

Cette expression définit une classe de fonctions qui ne croissent pas plus vite que g(n) jusqu'à un facteur constant.

Exemples de fonctions asymptotiques
f(n) g(n)
2n 2 + 7n - 3 n°2
98n*ln(n) n*ln(n)
5n+2 n
8 1
Ω – estimation pour le meilleur des cas

La définition est similaire à l'estimation du pire cas, cependant
f(n) = Ω(g(n)), Si
0 < c*g(n) < f(n)


Ω(g(n)) définit une classe de fonctions qui ne croissent pas plus lentement que la fonction g(n) jusqu'à un facteur constant.

Θ – estimation pour le cas moyen

Il convient seulement de mentionner que dans ce cas, la fonction f(n)à n > n 0 partout est entre c 1 *g(n) Et c 2 *g(n), où c est un facteur constant.
Par exemple, quand f(n) = n2 + n; g(n) = n2.

Critères d'évaluation de la complexité des algorithmes

Critère de poids uniforme (UWC) suppose que chaque étape de l'algorithme est effectuée dans une unité de temps et une cellule mémoire dans une unité de volume (jusqu'à une constante).
Critère de poids logarithmique (LWC) prend en compte la taille de l'opérande traité par une opération particulière et la valeur stockée dans la cellule mémoire.

Difficulté de temps pour DEX déterminé par la valeur élaguer), Où O p– valeur de l'opérande.
Complexité capacitive en LVK déterminé par la valeur l(M), Où M– taille de la cellule mémoire.

Un exemple d'estimation de la complexité lors du calcul factoriel

Il est nécessaire d'analyser la complexité de l'algorithme de calcul factoriel. Pour ce faire, écrivons cette tâche en pseudocode C :

Void main() ( int résultat = 1; int i; const n = ...; pour (i = 2; i<= n; i++) result = result * n; }

Complexité temporelle avec critère de pondération uniforme

Il suffit simplement de déterminer que la taille d’entrée d’un problème donné est n.
Nombre d'étapes - (n-1).

Ainsi, la complexité temporelle sous RVC est égale à Sur).

Complexité temporelle avec critère de pondération logarithmique

À ce stade, vous devez mettre en évidence les opérations qui doivent être évaluées. Il s’agit tout d’abord d’opérations de comparaison. Deuxièmement, les opérations de changement de variables (addition, multiplication). Les opérations d'affectation ne sont pas prises en compte car elles sont supposées instantanées.

Ainsi, dans cette tâche, il y a trois opérations :

1) je<= n

À la ième étape, il s'avère journal(n).
Depuis les étapes (n-1), la complexité de cette opération sera (n-1)*log(n).

2) je = je + 1

À la ième étape, il s'avère journal(i).
.

3) résultat = résultat * je

À la ième étape, il s'avère journal((i-1)!).
La somme est donc .

Si vous additionnez toutes les valeurs résultantes et écartez les termes qui croissent évidemment plus lentement avec l'augmentation n, on obtient l'expression finale .

Complexité capacitive avec critère de poids uniforme

Tout est simple ici. Il faut compter le nombre de variables. Si le problème utilise des tableaux, chaque cellule du tableau est considérée comme une variable.
Puisque le nombre de variables ne dépend pas de la taille de l’entrée, la complexité sera égale à O(1).

Complexité capacitive avec critère de poids logarithmique

Dans ce cas, vous devez prendre en compte la valeur maximale pouvant être stockée dans une cellule mémoire. Si la valeur n'est pas définie (par exemple, lorsque l'opérande i > 10), alors on suppose qu'il existe une sorte de valeur limite Vmax.
Dans ce problème, il existe une variable dont la valeur ne dépasse pas n(je), et une variable dont la valeur ne dépasse pas n! (résultat). Le score est donc O(log(n!)).

conclusions

Étudier la complexité des algorithmes est une tâche fascinante. À l'heure actuelle, l'analyse des algorithmes les plus simples est incluse dans les programmes de spécialités techniques (pour être précis, la direction généralisée « Informatique et informatique ») engagées dans l'informatique et les mathématiques appliquées dans le domaine de l'informatique.
En fonction de leur complexité, on distingue différentes classes de tâches : P., NP, PNJ. Mais ce n’est plus un problème dans la théorie de l’analyse asymptotique des algorithmes.

Temps constant

On dit qu'un algorithme est un algorithme temps constant(enregistré sous forme de temps O(1)), si la valeur T(n) est limité à une valeur indépendante de la taille de l'entrée. Par exemple, récupérer un élément dans un tableau prend un temps constant car une seule commande est exécutée pour le localiser. Cependant, trouver la valeur minimale dans un tableau non trié n’est pas une opération à temps constant puisqu’il faut parcourir chaque élément du tableau. Ainsi, cette opération prend un temps linéaire, O(n). Si le nombre d'éléments est connu à l'avance et ne change pas, un tel algorithme peut être qualifié d'algorithme à temps constant.

Malgré le nom de « temps constant », le temps d'exécution ne doit pas nécessairement être indépendant de la taille du problème, mais la limite supérieure du temps d'exécution ne doit pas nécessairement être indépendante. Par exemple, la tâche « échanger des valeurs un Et b, si nécessaire, pour que le résultat soit un≤b", est considéré comme un problème en temps constant, bien que le temps d'exécution de l'algorithme puisse dépendre du fait que l'inégalité soit déjà vraie un ≤ b ou non. Il existe cependant une certaine constante t, pour laquelle le temps d'exécution de la tâche est toujours ne dépasse pas t.

Vous trouverez ci-dessous quelques exemples de code exécutés en temps constant :

Indice int = 5 ; int élément = liste ; si(la condition est vraie) alorsautre effectuer certaines opérations avec un temps d'exécution constant pour je = 1 à 100 pour j = 1 à 200 effectuent certaines opérations avec un temps d'exécution constant

Si T(n) est égal à O( une valeur constante), c'est équivalent T(n) est O(1).

Temps logarithmique

temps logarithmique, Si T(n) = O(journal n) . Étant donné que les ordinateurs utilisent un système de nombres binaires, 2 est utilisé comme base du logarithme (c'est-à-dire log 2 n). Cependant, quand remplacement du socle les logarithmes enregistrent un n et connectez-vous b n ne diffèrent que par un facteur constant, qui est écarté dans la notation O-big. Alors O(log n) est la notation standard pour les algorithmes de temps logarithmique, quelle que soit la base du logarithme.

Les algorithmes qui s'exécutent en temps logarithmique sont couramment rencontrés lors de l'exécution d'opérations sur des arbres binaires ou lors de l'utilisation d'une recherche binaire.

Les algorithmes O(log n) sont considérés comme très efficaces car le temps de fonctionnement par élément diminue à mesure que le nombre d'éléments augmente.

Un exemple très simple d'un tel algorithme consiste à diviser une chaîne en deux, la seconde moitié est à nouveau divisée en deux, et ainsi de suite. Cela prend un temps O(log n) (où n est la longueur de la chaîne, nous supposons ici que console.log Et str.substring prendre un temps constant). Cela signifie que pour augmenter le nombre d'impressions, la longueur de la ligne doit être doublée.

// Fonction pour imprimer récursivement la moitié droite d'une ligne var right = fonction (str) (var length = str. length; // fonction d'assistance var help = fonction (index) ( // Récursion : imprimer la moitié droite si (indice< length ) { // Affiche les caractères de l'index jusqu'à la fin de la ligne console. log(str. substring(index, longueur)); // appel récursif : appelle la fonction auxiliaire avec le côté droit help (Math . ceil ((length + index ) / 2 )); ) ) aide ( 0 ); )

Temps polylogue

On dit que l'algorithme s'exécute dans temps polylogique, Si T(n) = O((journal n) k), pour certains k. Par exemple, le problème de l’ordre de multiplication matricielle peut être résolu en temps polylogarithmique par machine RAM parallèle .

Temps sublinéaire

On dit que l'algorithme s'exécute dans temps sublinéaire, Si T(n) = o( n). En particulier, cela inclut les algorithmes de complexité temporelle répertoriés ci-dessus, ainsi que d'autres tels que la recherche de Grover avec complexité O( n ½).

Les algorithmes typiques qui, bien que précis, fonctionnent toujours en temps sublinéaire, utilisent la parallélisation des processus (comme le fait l'algorithme NC 1 pour calculer le déterminant d'une matrice), des calculs non classiques (comme dans la recherche de Grover) ou ont une hypothèse garantie sur la structure de l'entrée (comme ceux fonctionnant en temps logarithmique, les algorithmes de recherche binaires et de nombreux algorithmes de traitement d'arborescence). Cependant, les constructions formelles, telles que l'ensemble de toutes les chaînes ayant un bit 1 dans la position déterminée par les premiers log(n) bits de la chaîne, peuvent dépendre de chaque bit de l'entrée mais rester sous-linéaires dans le temps.

Terme algorithme avec temps d'exécution sublinéaire généralement utilisé pour les algorithmes qui, contrairement aux exemples ci-dessus, fonctionnent sur des modèles de machines séquentiels ordinaires et ne supposent pas de connaissance a priori de la structure d'entrée. Cependant, l'utilisation de méthodes probabilistes est autorisée pour eux, et de plus, les algorithmes doivent être probabilistes pour la plupart des problèmes triviaux.

Puisqu’un tel algorithme doit produire une réponse sans lire entièrement les données d’entrée, il dépend fortement des méthodes d’accès autorisées dans le flux d’entrée. Généralement pour un flux qui est une chaîne de bits b 1 ,...,bb, on suppose que l'algorithme peut demander une valeur en un temps O(1) b je pour tout le monde je.

Les algorithmes temporels sublinéaires sont généralement probabilistes et ne fournissent qu’une solution approximative. Les algorithmes d'exécution sublinéaires apparaissent naturellement lors de la recherche contrôles de propriété.

Temps linéaire

temps linéaire, ou O( n) , si sa complexité est O( n). De manière informelle, cela signifie que pour une taille d'entrée suffisamment grande, le temps d'exécution augmente linéairement avec la taille de l'entrée. Par exemple, une procédure qui additionne tous les éléments d’une liste nécessite un temps proportionnel à la longueur de la liste. Cette description n'est pas tout à fait exacte, car le temps de fonctionnement peut différer considérablement de la proportionnalité exacte, en particulier pour les petites valeurs. n.

Le temps linéaire est souvent considéré comme un attribut souhaitable d’un algorithme. De nombreuses recherches ont été effectuées pour créer des algorithmes avec un temps d'exécution (presque) linéaire ou mieux. Ces études incluaient à la fois des approches logicielles et matérielles. Dans le cas de l'exécution matérielle, certains algorithmes qui, d'un point de vue mathématique, ne peuvent jamais atteindre un temps d'exécution linéaire dans les modèles informatiques standards, peuvent s'exécuter en temps linéaire. Certaines technologies matérielles utilisent le parallélisme pour atteindre cet objectif. Un exemple est la mémoire associative. Ce concept de temps linéaire est utilisé dans les algorithmes de comparaison de chaînes tels que l'algorithme de Boyer-Moore et l'algorithme d'Ukkonen.

Temps quasi-linéaire

On dit que l’algorithme s’exécute en temps quasi-linéaire si T(n) = O( n enregistrer k n) pour une constante k. Le temps linéaire-logarithmique est un cas particulier avec k= 1 . En utilisant la notation faible-O, ces algorithmes sont Õ( n). Les algorithmes temporels quasi-linéaires sont également o( n 1+ε) pour tout ε > 0 et travaille plus vite que n’importe quel polynôme dans n

Les algorithmes qui s'exécutent en temps quasi-linéaire, en plus des algorithmes linéaires-logarithmiques mentionnés ci-dessus, comprennent :

  • Tri par fusion sur place, O( n enregistrer 2 n)
  • Tri rapide, O( n enregistrer n), dans la version probabiliste, a un temps d'exécution dans le pire des cas linéaire-logarithmique. La version non probabiliste a un temps d'exécution linéaire-logarithmique uniquement pour mesurer la complexité en moyenne.
  • Tri en tas, O( n enregistrer n), tri par fusion, tri par introduction, tri par arbre binaire, tri fluide, tri solitaire, etc. au pire
  • Transformations de Fourier rapides, O( n enregistrer n)
  • Calcul des matrices de Monge, O( n enregistrer n)

Temps linéaire-logarithmique

Le logarithmique linéaire est un cas particulier de temps quasi-linéaire avec l'exposant k= 1 sur le terme logarithmique.

Fonction linéaire-logarithmique est fonction de la forme n enregistrer n(c'est-à-dire le travail linéaire et termes logarithmiques). On dit que l'algorithme fonctionne dans temps linéaire-logarithmique, Si T(n) = O( n enregistrer n) . Ainsi, le terme logarithmique linéaire croît plus vite que le terme linéaire, mais plus lentement que n'importe quel polynôme de n de degré strictement supérieur à 1.

Dans de nombreux cas, la durée de fonctionnement n enregistrer n est simplement le résultat de l’exécution de l’opération Θ(log n) n une fois. Par exemple, le tri par arbre binaire crée un arbre binaire en insérant chaque élément dans un tableau de taille n l'un après l'autre. Depuis l’opération d’insertion dans arbre de recherche binaire équilibré prend un temps O(log) n), le temps total d'exécution de l'algorithme sera linéaire-logarithmique.

Tris de comparaison nécessitent au moins un nombre linéaire-logarithmique de comparaisons pour le pire des cas, puisque log( n!) = Θ( n enregistrer n) selon la formule de Stirling. Le même temps d'exécution résulte souvent de l'équation de récurrence T(n) = 2 T(n/2) + O( n).

Temps sous-quadratique

Quelques exemples d'algorithmes en temps polynomial :

Temps strictement et faiblement polynomial

Dans certains contextes, notamment en optimisation, on distingue les algorithmes avec temps polynomial strict Et temps faiblement polynomial. Ces deux concepts s'appliquent uniquement aux entrées entières.

Le temps strictement polynomial est défini dans le modèle arithmétique de calcul. Dans ce modèle, les opérations arithmétiques de base (addition, soustraction, multiplication, division et comparaison) sont considérées comme unités d'exécution, quelle que soit la longueur des opérandes. L'algorithme s'exécute en temps strictement polynomial si

  1. le nombre d'opérations dans le modèle de calcul arithmétique est limité par un polynôme dans le nombre d'entiers dans le flux d'entrée, et
  2. La mémoire utilisée par l'algorithme est limitée par un polynôme de la taille d'entrée.

Tout algorithme possédant ces deux propriétés peut être réduit à un algorithme en temps polynomial en remplaçant les opérations arithmétiques par les algorithmes correspondants pour effectuer des opérations arithmétiques sur une machine de Turing. Si la deuxième des conditions ci-dessus n’est pas remplie, cela ne sera plus vrai. Étant donné un entier (qui occupe une mémoire proportionnelle à n dans une machine de Turing), il peut être calculé avec n opérations en utilisant une exponentiation répétée. Cependant, la mémoire utilisée pour la représentation 2 2 n (\style d'affichage 2^(2^(n))), proportionnel 2 n (\style d'affichage 2^(n)), et cela dépend de manière exponentielle plutôt que polynomiale de la mémoire utilisée pour l'entrée. Il est donc impossible d’effectuer ces calculs en temps polynomial sur une machine de Turing, mais ils peuvent être effectués en un nombre polynomial d’opérations arithmétiques.

À l'inverse, il existe des algorithmes qui fonctionnent dans le nombre d'étapes de la machine de Turing limité par la longueur polynomiale de l'entrée codée en binaire, mais ne fonctionnent pas dans le nombre d'opérations arithmétiques limitées par un polynôme dans le nombre de nombres dans l'entrée. L'algorithme d'Euclide pour calculer le plus grand commun diviseur de deux nombres entiers en est un exemple. Pour deux entiers une (\style d'affichage a) Et b (style d'affichage b) La durée d’exécution de l’algorithme est limitée O ((log ⁡ a + log ⁡ b) 2) (\displaystyle O((\log \ a+\log \ b)^(2)))étapes d'une machine de Turing. Ce nombre est un polynôme de la taille de la représentation binaire des nombres une (\style d'affichage a) Et b (style d'affichage b), ce qui peut être grossièrement représenté par journal ⁡ a + journal ⁡ b (\displaystyle \log \a+\log \b). Dans le même temps, le nombre d'opérations arithmétiques ne peut pas être limité au nombre d'entiers en entrée (qui dans ce cas est une constante - il n'y a que deux nombres en entrée). De ce fait, l’algorithme ne fonctionne pas en temps strictement polynomial. Le temps d'exécution réel de l'algorithme dépend des quantités une (\style d'affichage a) Et b (style d'affichage b), et pas seulement le nombre d'entiers dans l'entrée.

Si un algorithme s’exécute en temps polynomial mais pas en temps strictement polynomial, on dit qu’il s’exécute en temps polynomial. temps faiblement polynomial. Un exemple bien connu de problème pour lequel un algorithme faiblement polynomial est connu, mais un algorithme strictement polynomial n'est pas connu, est la programmation linéaire. Le temps faiblement polynomial ne doit pas être confondu avec le temps pseudopolynomial.

Cours de difficulté

Le concept de temps polynomial conduit à plusieurs classes de complexité dans la théorie de la complexité computationnelle. Certaines classes importantes définies en utilisant le temps polynomial sont données ci-dessous.

  • : Classe de problèmes de solvabilité pouvant être résolus dans une machine de Turing déterministe en temps polynomial.
  • : La classe de complexité des problèmes de solvabilité qui peuvent être résolus dans une machine de Turing non déterministe en temps polynomial.
  • ZPP: La classe de complexité des problèmes de solvabilité qui peuvent être résolus avec zéro erreur dans une machine de Turing probabiliste en temps polynomial.
  • : La classe de complexité des problèmes de solvabilité qui peuvent être résolus avec des erreurs unilatérales dans une machine de Turing probabiliste en temps polynomial.
  • BPP Machine de Turing probabiliste en temps polynomial.
  • BQP: La classe de complexité des problèmes de solvabilité qui peuvent être résolus avec des erreurs bidirectionnelles dans une machine de Turing quantique en temps polynomial.

P est la plus petite classe de complexité temporelle sur une machine déterministe, qui est durable en termes de changement de modèle de voiture. (Par exemple, passer d'une machine de Turing à bande unique à une machine de Turing à bandes multiples peut entraîner une accélération quadratique, mais tout algorithme qui s'exécute en temps polynomial sur un modèle s'exécutera en temps polynomial sur l'autre.)

Temps superpolynomial

On dit que l'algorithme fonctionne dans temps superpolynomial, Si T(n) n’est pas borné au dessus par un polynôme. Ce temps est égal à ω( n c) pour toutes les constantes c, Où n- paramètre d'entrée, généralement le nombre de bits d'entrée.

Par exemple, un algorithme qui implémente 2 nétapes pour saisir la taille n nécessite un temps superpolynomial (plus précisément un temps exponentiel).

Clairement, un algorithme utilisant des ressources exponentielles est superpolynomial, mais certains algorithmes sont très faiblement superpolynomiaux. Par exemple, Test de simplicité Adleman-Pomeranz-Roumeli*ça marche pour le temps n O (journal journal n) sur n-entrée de bits. Cela croît plus vite que n'importe quel polynôme suffisamment grand n, mais la taille d'entrée doit devenir très grande pour qu'elle ne soit pas dominée par le polynôme de bas degré.

Un algorithme nécessitant un temps superpolynomial se situe en dehors de la classe de complexité. La thèse de Cobham soutient que ces algorithmes ne sont pas pratiques, et ils le sont dans de nombreux cas. Le problème de l'égalité des classes P et NP n'ayant pas été résolu, aucun algorithme permettant de résoudre des problèmes NP-complets en temps polynomial n'est actuellement connu.

Temps quasi polynomial

Algorithmes temps quasi polynomial sont des algorithmes qui s'exécutent plus lentement que le temps polynomial, mais pas aussi lents que les algorithmes à temps exponentiel. Le temps d’exécution le plus défavorable pour l’algorithme quasi-polynomial est c. Un algorithme classique bien connu pour factoriser un entier, , Pas est quasi-polynomial, puisque le temps d'exécution ne peut pas être représenté comme 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c)))) pour certains fixes c. Si la constante "c" dans la définition d'un algorithme temporel quasi-polynomial est 1, on obtient un algorithme temporel polynomial, et si elle est inférieure à 1, on obtient un algorithme temporel sous-linéaire.

Les algorithmes en temps quasi polynomial surviennent généralement lors de la réduction d'un problème NP-difficile à un autre problème. Par exemple, vous pouvez prendre un problème NP-difficile, disons 3SAT, et le réduire à un autre problème B, mais la taille du problème devient 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c)))). Dans ce cas, la réduction ne prouve pas que le problème B est NP-difficile, elle montre seulement qu'il n'y a pas d'algorithme polynomial pour B à moins qu'il n'existe un algorithme quasi-polynomial pour 3SAT (et donc pour tous les problèmes). De même, il existe certains problèmes pour lesquels nous connaissons des algorithmes en temps quasi-polynomial, mais pour lesquels nous ne connaissons pas d'algorithmes en temps polynomial. De tels problèmes apparaissent dans les algorithmes d’approximation. Un exemple célèbre est le problème orienté de Steiner, pour lequel il existe un algorithme d'approximation quasi-polynomial avec un coefficient d'approximation O (log 3 ⁡ n) (\displaystyle O(\log ^(3)n))(où n est le nombre de sommets), mais l'existence d'un algorithme en temps polynomial est un problème ouvert.

Classe de difficulté QP se compose de tous les problèmes qui ont des algorithmes temporels quasi-polynomiaux. Il peut être défini en termes de DTIME comme suit

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\displaystyle (\mbox(QP))=\bigcup _(c\in \mathbb (N) )(\mbox(DTIME))(2^ ((\log n)^(c))))

Connexion avec des problèmes NP-complets

Dans la théorie de la complexité, le problème non résolu de l'égalité entre les classes P et NP demande si tous les problèmes de la classe NP ont des algorithmes de résolution en temps polynomial. Tous les algorithmes bien connus pour les problèmes NP-complets, comme 3SAT, ont un temps exponentiel. De plus, il existe une hypothèse selon laquelle pour de nombreux problèmes naturels NP-complets, il n’existe pas d’algorithmes avec un temps d’exécution sous-exponentiel. Ici, le « temps sous-exponentiel » est pris au sens de la deuxième définition donnée ci-dessous. (D'un autre côté, de nombreux problèmes de théorie des graphes, naturellement représentés par des matrices d'adjacence, peuvent être résolus en temps sous-exponentiel simplement parce que la taille de l'entrée est égale au carré du nombre de sommets.) Cette conjecture (pour le k- problème SAT) est connu sous le nom hypothèse du temps exponentiel. Puisqu'il suppose que les problèmes NP-complets n'ont pas d'algorithmes en temps quasi-polynomial, certains résultats d'inapproximation dans le domaine des algorithmes d'approximation supposent que les problèmes NP-complets n'ont pas d'algorithmes en temps quasi-polynomial. Par exemple, voir les résultats bien connus sur la non-approximation du problème de recouvrement d'ensembles.

Temps sous-exponentiel

Terme sous-exponentiel temps est utilisé pour exprimer que le temps d'exécution de certains algorithmes peut croître plus rapidement que n'importe quel polynôme, mais reste nettement inférieur à l'exponentiel. En ce sens, les problèmes utilisant des algorithmes à temps sous-exponentiel sont plus faciles à résoudre que les algorithmes utilisant uniquement un temps exponentiel. La définition exacte de « subexponentiel » n'est pas encore généralement acceptée, et nous présentons ci-dessous les deux définitions les plus courantes.

Première définition

Un problème est dit résolu en temps sous-exponentiel s’il est résolu par un algorithme dont le logarithme du temps d’exécution croît moins que n’importe quel polynôme donné. Plus précisément, un problème a un temps sous-exponentiel si pour tout ε > 0 il existe un algorithme qui résout le problème en un temps O(2 n ε). L’ensemble de ces problèmes constitue la classe de complexité SOUS-EXP, qui en termes de DTIME peut être exprimé par .

SUBEXP = ⋂ ε > 0 DTIME (2 n ε) (\displaystyle (\text(SUBEXP))=\bigcap _(\varepsilon >0)(\text(DTIME))\left(2^(n^(\varepsilon ))\droite))

Notez qu'ici ε ne fait pas partie des données d'entrée et pour chaque ε il peut y avoir son propre algorithme pour résoudre le problème.

Deuxième définition

Certains auteurs définissent le temps sous-exponentiel comme un temps d'exécution de 2 o( n) . Cette définition permet des durées d'exécution plus longues que la première définition. Un exemple d'un tel algorithme de temps sous-exponentiel est l'algorithme classique bien connu de factorisation d'entiers, la méthode générale de tamisage de champs de nombres, qui s'exécute en environ 2 O ~ (n 1 / 3) (\displaystyle 2^((\tilde (O))(n^(1/3)))), où la longueur d'entrée est n. Un autre exemple est l'algorithme bien connu pour problèmes d'isomorphisme des graphes, dont la durée de fonctionnement est égale à 2 O ((n log ⁡ n)) (\displaystyle 2^(O((\sqrt (())n\log n)))).

Notez que cela fait une différence si l'algorithme est sous-exponentiel en termes de nombre de sommets ou de nombre d'arêtes. DANS complexité paramétrée cette différence est rendue explicite en spécifiant le couple , le problème de solvabilité et le paramètre k. SOUS-PT est la classe de toutes les tâches paramétrées qui s'exécutent en un temps sous-exponentiel dans k et pour un polynôme dans n :

SUBEPT = DTIME (2 o (k) ⋅ poly (n)) . (\displaystyle (\text(SUBEPT))=(\text(DTIME))\left(2^(o(k))\cdot (\text(poly))(n)\right).)

Plus précisément, SUBEPT est la classe de toutes les tâches paramétrées (L , k) (\displaystyle (L,k)), pour lequel il existe une fonction calculable f : N → N (\displaystyle f:\mathbb (N) \to \mathbb (N) ) Avec f ∈ o (k) (\displaystyle f\in o(k)) et un algorithme qui résout L pendant 2 f (k) ⋅ poly (n) (\displaystyle 2^(f(k))\cdot (\text(poly))(n)).

Pour comparer des algorithmes, il est d'usage d'utiliser une caractéristique généralisée appelée efficacité. On dit que l'algorithme L, plus efficace algorithme Un 2, si l'algorithme est L, il s'exécute en moins de temps et (ou) nécessite moins de ressources informatiques (RAM, espace disque, trafic réseau, etc.).

Un algorithme efficace doit satisfaire aux exigences de temps d’exécution acceptable et de consommation raisonnable de ressources, comme déjà mentionné au paragraphe 1.1. La combinaison de ces caractéristiques constitue la notion de complexité algorithmique. Plus le temps d’exécution de l’algorithme et/ou les ressources impliquées augmentent, plus la complexité augmente. Ainsi, les concepts d’efficacité et de complexité sont inverses l’un de l’autre.

La caractéristique d'un algorithme qui reflète le temps consacré à sa mise en œuvre s'appelle complexité temporelle. La caractéristique d'un algorithme, reflétant les coûts en ressources informatiques de sa mise en œuvre, est appelée complexité capacitive.

Dans les évaluations quantitatives et qualitatives de l'algorithme liées à la détermination de la complexité, deux approches sont utilisées : pratique et théorique.

Approche pratique associés à l’exécution d’algorithmes sur des appareils physiques spécifiques. Il se caractérise par des paramètres mesurables et enregistrés. La complexité temporelle dans cette approche peut être exprimée en unités de temps (par exemple, en millisecondes) ou en nombre de cycles de processeur consacrés à l'exécution de l'algorithme. La complexité capacitive peut être exprimée en bits (ou autres unités d'information), en configuration matérielle minimale requise pour exécuter l'algorithme, etc.

L’évaluation pratique n’est pas un indicateur absolu de l’efficacité de l’algorithme. Les valeurs quantitatives obtenues grâce à cette approche dépendent de nombreux facteurs, tels que :

  • caractéristiques techniques des composants qui composent le système informatique. Ainsi, plus la fréquence d'horloge du processeur est élevée, plus les opérations élémentaires peuvent être effectuées par unité de temps ;
  • caractéristiques de l'environnement logiciel (nombre de processus en cours d'exécution, algorithme du planificateur de tâches, fonctionnalités du système d'exploitation, etc.) ;
  • le langage de programmation sélectionné pour implémenter l'algorithme. Un programme écrit dans un langage de haut niveau s'exécutera probablement plus lentement et nécessitera plus de ressources qu'un programme écrit dans des langages de bas niveau ayant un accès direct aux ressources matérielles ;
  • expérience du programmeur qui a implémenté l'algorithme. Très probablement, un programmeur débutant écrira un programme moins efficace qu’un programmeur expérimenté.

Ainsi, un algorithme exécuté sur le même système informatique pour les mêmes données d’entrée peut avoir des estimations quantitatives différentes à différents moments. Par conséquent, une approche théorique pour définir la complexité est plus importante.

Complexité théorique caractérise l'algorithme sans référence à du matériel, des logiciels et des outils de mise en œuvre spécifiques. Dans ce cas, la complexité temporelle s'exprime en nombre d'opérations, de cycles de fonctionnement de la machine de Turing, etc. La complexité capacitive est déterminée par le volume de données (entrée, intermédiaire, sortie), le nombre de cellules impliquées sur la bande de la machine Thjoring, etc.

Dans une approche théorique de l'évaluation de l'efficacité, on suppose que l'algorithme est exécuté à un moment donné. ordinateur idéalisé, pour lequel le temps d'exécution de chaque type d'opération est connu et constant. On pense également que les ressources d'un tel ordinateur sont infinies, de sorte que la complexité capacitive n'est généralement pas déterminée par une approche théorique. Le nombre d'instructions (opérations) effectuées sur un ordinateur idéalisé est choisi comme caractéristique temporelle de la complexité.

Les estimations quantitatives obtenues à l'aide d'une approche théorique peuvent également dépendre d'un certain nombre des facteurs suivants :

  • volume de données d’entrée. Plus il est grand, plus il faudra de temps pour exécuter l'algorithme ;
  • la méthode choisie pour résoudre le problème. Par exemple, pour une grande quantité de données d’entrée, l’algorithme de tri rapide est plus efficace que l’algorithme de tri à bulles, bien qu’il produise le même résultat.

Le temps d'exécution de l'algorithme dépend généralement du volume des données d'entrée (taille de l'entrée), qui est compris comme la dimension du problème à résoudre. Ainsi, lors du tri d'un ensemble de valeurs, le volume de données est le nombre d'éléments de cet ensemble. Lors du traitement de chaînes, la taille des données d'entrée correspond à la longueur de la chaîne.

Laisser P- la quantité de données d'entrée pour un algorithme. Notons par T(p) le nombre d'instructions exécutées sur un ordinateur idéalisé lors de l'exécution d'un algorithme, et il est déterminé pour le « pire des cas » lorsque le volume d'opérations est maximum.

La notion de « pire cas » peut être illustrée par un exemple. Considérons un algorithme permettant de vérifier la présence d'un élément numérique dans un certain ensemble (tableau) de nombres. Si cet ensemble est ordonné par ordre croissant, alors, d'une manière générale, il ne sert à rien de vérifier les éléments situés après le premier élément supérieur à celui recherché. Dans ce cas T(p) etc. Cependant, dans le pire des cas (pour un ensemble arbitraire non trié), vous devrez parcourir tous les éléments de l'ensemble. Evidemment ici T(p) = p.

En général, T(p) est une fonction de la quantité de données d'entrée P. Dans de nombreux cas T(p) exprimé sous forme de fonction polynomiale, puissance ou logarithmique de P.

Comportement de la quantité T(p) en fonction du grossissement P. appelé complexité asymptotique algorithme. Ils disent ça T(p) Il a ordre de complexité 0(J(n))(lit "À PROPOS grand de/de P") pour un algorithme, s'il y a des constantes Avec et volume de données sch tel que HAUT > n 0 et il y a des inégalités T(p) s/(p).

Ce fait s'écrit T(n) = 0(J(n)) et signifie que pour la fonction T(p) il existe une telle fonction f(n) et une constante c, pour laquelle, à partir de quelque n 0, signification T(p) ne dépasse pas cf(n).

Fonction f(n) représente la limite supérieure des valeurs de la fonction T(p). Laissez, par exemple, T(n) = 2p.A. + numéro 2. Sélection de valeurs n°0= 0 et c = 5, pour tout le monde n > n 0 nous avons T(n) = 2p.A. + n°2 T(n) est d'ordre i 4.

Fonction T(p) est associé à un algorithme spécifique, on dit donc souvent que l'ordre de complexité 0(/(n)) a exactement l'algorithme.

Ils disent ça T(p) Il a borne inférieure Q(g(n))(lit "oméga gros de g from /g"), si la constante c et la quantité de données existent n°0 tel que /P et il y a des inégalités T(n) > cg(n).

Ce fait s'écrit T(n) = Q(g(n)). Laissez, par exemple, T(n) = 2ème 4 + numéro 2. Sélection de la valeur c = 1, pour tout le monde P. nous avons T(p)= 2ème 4 + p 2 > sp A > ainsi, T(p) a une borne inférieure i 4 .

Il est facile de voir que l’ordre et la limite inférieure ne sont pas uniques pour certaines fonctions T(p). Dans les exemples ci-dessus, on pourrait choisir i 5 , i 6 ,... comme /(i), et comme g(n)- i 3, i 2,.... Habituellement, la fonction avec le degré minimum est choisie comme /(i), et comme g(n)- avec un maximum.

L'ordre de complexité 0(/(i)) et la borne inférieure Q(g(rc)) représentent des classes de fonctions. Intuitivement, Q(g"(n)) peut être compris comme une classe de fonctions croissant au moins aussi vite que T(p). De même, intuitivement 0(f(n)) peut être compris comme une classe de fonctions qui ne croissent pas plus vite que T(p). AVEC D'un point de vue pratique, lors de l'évaluation de la complexité d'un algorithme, le plus important est la classe de fonctions 0(f(n)). Déterminer le type de fonction /(i) est tâche principale du calcul complexité théorique de l'algorithme.

Pour tout algorithme, lors de la détermination du degré de croissance, vous pouvez utiliser les propriétés suivantes de 0(/(i)) :

1) 0(kf(ji))= 0(/(i)), où k= const. Ainsi, le multiplicateur constant de la fonction n’affecte pas le taux de croissance. Par exemple,

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)). Ainsi, l’ordre du produit de deux fonctions est égal au produit de leurs complexités. Par exemple,

Parfois, cette propriété s’écrit

3) 0(/(p) + g(n))équivaut à dominant(fonctions avec degré maximum) fonctions /(i) et g(n). Par exemple,

Dans la théorie de la complexité des algorithmes, on distingue les classes de fonctions de complexité suivantes :

  • 1) complexité constante 0(1). Le temps d'exécution de l'algorithme et les ressources utilisées ne dépendent pas de la quantité de données d'entrée. Généralement, les algorithmes qui ne contiennent pas de boucles ni d'appels récursifs ont cette complexité ;
  • 2) complexité linéaire 0(n). Typiquement, une telle complexité se retrouve dans les tâches dans lesquelles chaque élément des données d'entrée doit être traité un certain nombre de fois, qui n'est en aucun cas lié au nombre de traitements d'autres éléments ;
  • 3) complexité logarithmique 0(log 2 w), 0(nong 2 n). D'autres bases logarithmiques sont parfois utilisées ;
  • 4) complexité polynomiale 0(i 2), 0(i 3), 0(i 4),... ;
  • 5) complexité exponentielle 14 heures, 3",....

À mesure que la taille d'entrée augmente, la complexité de chaque type de fonction suivant augmente plus rapidement que le précédent (sauf pour 0(log 2 /?)). Pour une quantité de données d’entrée suffisamment importante, il est préférable d’utiliser des algorithmes moins complexes.

Lors du calcul quantitatif de la complexité, une opération ou un groupe d'opérations significatif pour cet algorithme (constitue sa base) est initialement sélectionné. Il s'agit généralement d'opérations de comparaison et d'opérations arithmétiques. Les opérations de comparaison consistent à vérifier les valeurs de deux quantités (inférieures à, supérieures à, égales à, inférieures ou égales, supérieures ou égales à, non égales à). Ils sont considérés comme équivalents en temps d’exécution. Les opérations arithmétiques, à leur tour, sont divisées en additif Et multiplicatif. Au premier (souvent appelé simplement ajout) inclure l'ajout, la soustraction, la décrémentation ou la décrémentation d'une valeur de compteur. Au second (appelé simplement multiplication) inclure la multiplication, la division, le modulo.

Les opérations d'addition sont plus rapides que les opérations de multiplication, c'est pourquoi les algorithmes avec moins de multiplications sont préférés, même si le nombre d'additions augmente proportionnellement au nombre de multiplications de diminution.

Les opérations de multiplication ou de division d'entiers par puissances de 2 sont classées comme opérations additives, car lorsqu'on travaille avec des cellules mémoire, elles sont réduites à un décalage, ce qui équivaut à l'opération d'addition.

Une fois les opérations significatives sélectionnées, elles sont réparties en deux catégories :

  • 1) les opérations qui affectent directement la complexité de l'algorithme ;
  • 2) les opérations qui constituent une « surcharge » lors de l'exécution de l'algorithme (par exemple, l'allocation de mémoire pour stocker des données intermédiaires).

Compter ou estimer directement le nombre d'opérations effectuées permet d'estimer T(p).

Pour estimer l'ordre de complexité, vous pouvez utiliser l'analyse du code du programme qui implémente l'algorithme. Où:

  • les algorithmes sans boucles ni appels récursifs ont une complexité d’ordre 0(1). Ainsi, les opérations d'affectation, les entrées et sorties de données et les structures conditionnelles ont une complexité constante ;
  • si deux parties du code du programme ont des difficultés 0(J((ri)) Et 0(J2(n)), alors l'exécution séquentielle est complexe
  • si le corps de la boucle est exécuté une fois pour chaque élément des données d'entrée, alors la complexité d'exécution de la boucle est de l'ordre de 0(n)0( 1) = 0(n);
  • l'ordre de complexité d'exécution des boucles imbriquées est calculé à l'aide de la règle du produit 0(J x (n)f 2 (n)) = 0(/,(/?))- 0(J2(ri)). Si chacun d'eux a une complexité de l'ordre 0(n), l'exécution de boucles imbriquées a une complexité de l'ordre de 0(n 2).

Exemple 1.3

Déterminer l'ordre de complexité d'un algorithme de programme dans un langage

Pascal présenté dans le listing 1.2. Les lignes du programme sont numérotées en commentaires (voir paragraphe 2.6).

Inscription 1.2

(01) pour i:=l à n faire

(02) commencer

(03) write("Entrez l'élément du tableau

avec l'indice ",i,": ");

(04) Readln(MonArray[i]);

(05)fin ;

(06) pour i:=l à n faire

(07) pour j:=1 à n faire

(08)commencer

(09) write("Entrez l'élément du tableau

avec les indices ", i, ",", j, " : ");

(10) Readln(MonDArray);

(11)fin ;

Solution

Les lignes 02, 05, 08, 11 ne contiennent pas d'instructions exécutables, elles ne sont donc pas prises en compte lors de la détermination de l'ordre.

Les lignes 03 et 04 ont l'ordre 0(1). Leur exécution séquentielle a l'ordre 0(1) + 0(1) = 0(1). De même, l’exécution séquentielle des lignes 09 et 10 a une complexité de 0(1).

La boucle des lignes 01-05 a une complexité d'ordre Sur), boucles imbriquées dans les lignes 06-11 - commande 0(n 2). La complexité finale de l'algorithme est de l'ordre

L'évaluation de la complexité de l'algorithme, à la fois en temps et en ressources, nous permet de déterminer le temps d'exécution maximum et moyen de l'algorithme. Ceci est extrêmement important lors du traitement de grandes quantités d’informations, en particulier dans les tâches de tri et de recherche décrites ci-dessous.

Fonction de difficulté 0(1). Dans les algorithmes à complexité constante, la plupart des opérations du programme sont effectuées une ou plusieurs fois. Tout algorithme qui nécessite toujours (quelle que soit la taille des données) le même temps a une complexité constante.

Fonction de complexité 0(N). La durée d'exécution d'un programme est généralement linéaire, chaque élément des données d'entrée ne devant être traité qu'un nombre linéaire de fois. Cette fonction de complexité caractérise un cycle simple.

Fonction de complexité 0(N 2), 0(N 3), 0(№) - fonction de complexité polynomiale : le nombre d'opérations augmente avec le carré N. Dans le cas général, cela peut être O(A^), selon la complexité du problème. Cette fonction de complexité caractérise un cycle complexe.

Fonction de difficulté O(Journal 2 (A0), 0(N log2(A0). C'est le moment où fonctionnent les algorithmes qui divisent un gros problème en plusieurs petits, puis, après les avoir résolus, combinent les solutions.

Fonction de complexité 0(e N). Les algorithmes à complexité exponentielle résultent le plus souvent d’une approche appelée force brute.

Fonction de complexité 0(M) - le nombre d'opérations augmente proportionnellement à la factorielle N.

Un programmeur doit être capable d'analyser les algorithmes et de déterminer leur complexité. La complexité temporelle d'un algorithme peut être calculée sur la base d'une analyse de ses structures de contrôle.

Les algorithmes sans boucles ni appels récursifs ont une complexité constante. S'il n'y a pas de récursion ni de boucles, toutes les structures de contrôle peuvent être réduites à des structures de complexité constante. Par conséquent, l’ensemble de l’algorithme se caractérise également par une complexité constante. Déterminer la complexité d’un algorithme revient principalement à analyser les boucles et les appels récursifs.

Par exemple, considérons un algorithme de traitement des éléments d'un tableau.

Pour /": = 1 à N faire commencer

Complexité de cet algorithme À PROPOS(A), puisque le corps de la boucle est exécuté A fois et que la complexité du corps de la boucle est de 0(1). Si une boucle est imbriquée dans une autre et que les deux boucles dépendent de la taille de la même variable, alors la conception entière est caractérisée par une complexité quadratique.

Pour / : = 1 à N faire pour j : = 1 à N faire commencer

La complexité de ce programme 0(N2).

Exemple 1. Estimons la complexité d'un programme qui saisit un tableau à partir du clavier et y trouve le plus grand élément. L'algorithme comprend les étapes suivantes :

  • - saisie d'un tableau (il faut lire les éléments A) ;
  • - rechercher le plus grand élément (il faut faire une comparaison A - 1) ;
  • - afficher le résultat (vous devez afficher un nombre ou une chaîne).

Additionnons le nombre d'opérations A + (A - 1) + 1 = 2A, c'est-à-dire existe

une constante telle que pour tout A, le nombre d'opérations ne dépasse pas CA. La complexité de l’algorithme est donc 0(A).

Exemple 2. Estimons la complexité d'un programme qui saisit un tableau à partir du clavier et y trouve un élément avec une propriété donnée (par exemple, égale à une certaine valeur). L'algorithme comprend les étapes suivantes :

  • - entrée de tableau (opérations d'entrée) ;
  • - rechercher un élément avec une propriété donnée (l'élément peut être situé soit plus près du début du tableau, soit à la toute fin ; si l'élément n'existe pas, alors toutes les comparaisons A doivent être faites pour s'en assurer) ;
  • - sortie du résultat.

Dans le meilleur des cas, l'algorithme spécifié nécessitera A + 2 opérations (entrée de l'ensemble du tableau, une seule comparaison, sortie), dans le pire des cas (lorsqu'un tel élément n'existe pas, 2A + 1 opération). Si A est un grand nombre, par exemple de l'ordre de 10 6, alors l'unité peut être négligée. La complexité de l’algorithme est donc égale à 0(N).

Exemple 3. Définissons la fonction de complexité de l'algorithme de chiffrement pour un mot de longueur L par méthode de substitution. Soit un tableau dans lequel pour chaque caractère de l'alphabet est écrit le caractère par lequel il doit être remplacé. Notons le nombre de lettres de l'alphabet S. L'algorithme comprend les étapes suivantes :

  • - saisir un mot (une opération) ;
  • - organisation du cycle :
    • 1) pour chaque caractère, trouvez son remplacement dans le tableau (si le tableau n'est pas ordonné et n'a aucune propriété facilitant la recherche, alors dans le pire des cas vous aurez besoin S opérations sur un caractère si l'élément recherché est à la toute fin) ;
    • 2) sortie du symbole trouvé ;
  • - fin du cycle.

Nombre total d'opérations 1 + (S+)L. En cas de quantité suffisamment importante S Et L les unités peuvent être négligées, et il s'avère que la fonction de complexité de l'algorithme donné est O(SL).

Exemple 4. Définissons la fonction de complexité de l'algorithme de traduction des nombres naturels 1 V au système de nombres binaires (sans opérations d'entrée et de sortie de données). L'algorithme comprend les étapes suivantes :

  • - boucler jusqu'à ce que le résultat de la division d'un nombre par 2 soit égal à 0 :
  • - divisez le nombre par 2 et mémorisez le reste ;
  • - prendre le résultat de la division comme un nouveau nombre ;
  • - fin du cycle.

Le nombre total d'opérations ne dépasse pas 1 + log 2 A. Par conséquent, l'algorithme décrit a la complexité 0(et 2 N).

Pour évaluer l'efficacité de l'algorithme, les indicateurs les plus importants sont :

Temps d'exécution de l'algorithme,
- quantité de RAM requise.

De nos jours, grâce à un demi-siècle de progrès technologique, le premier indicateur (le temps d'exécution) est souvent beaucoup plus important que le second, nous n'y reviendrons donc que plus en détail.

Simplifications pour estimer le temps d'exécution des algorithmes

Dans les travaux de D. Knuth, l'approche suivante a été proposée pour analyser le temps d'exécution des algorithmes : le temps total est constitué des valeurs de coût * fréquence pour chaque opération de base. Les opérations de base peuvent inclure l'addition, la multiplication, la division, l'obtention d'un élément par index à partir d'un tableau, la comparaison d'entiers, etc. Il est facile de constater que dans ce cas, calculer une estimation du temps d’exécution de l’algorithme est assez fastidieux. Par conséquent, A. Turing a déclaré qu'il est pratique d'utiliser même des approximations grossières des estimations du temps d'exécution des algorithmes : vous pouvez attribuer des poids à diverses opérations en fonction de leur fréquence d'occurrence pendant le fonctionnement de l'algorithme et prendre en compte uniquement ces opérations qui ont les poids les plus élevés. Par exemple, lors de la multiplication de matrices, seules les opérations telles que la multiplication et l'écriture de nombres doivent être prises en compte, car Ce sont les opérations les plus courantes.En considérant seulement le plusopérations fréquentes - première simplification, proposé pour le calcul approximatif du temps d'exécution des algorithmes.

La deuxième simplification consiste à éliminer les termes d’ordre inférieur (c’est-à-dire les termes) qui contribuent peu au temps d’exécution global de l’algorithme. Par exemple (ci-après le nombre N caractérise la taille des données d'entrée),

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),

au lieu de \(1/6N^3\) ils écrivent "cet algorithme a une complexité \(O(N^3)\), au lieu de \(3N^4\) ils écrivent "cet algorithme a une complexité \(O(N ^4)\ )".

Définition de Big O

On dit que \(f\) est "O grand" de \(g\) pour \(x \to x_0\) s'il existe une constante \(C>0\) telle que pour tout \(x\) à partir d'un voisinage du point \(x_0\), l'inégalité \(|f(x)| \leq C|g(x)|\) est vraie. Vous trouverez ci-dessous une illustration de la définition (l'axe \(x\) est la taille des données d'entrée, l'axe \(y\) est le temps d'exécution de l'algorithme). Nous voyons qu'à partir d'un certain point, à mesure que la taille des données d'entrée tend vers \(\propto\) \(f(n)\) croît plus lentement que \(g(n)\) et en général \(g (n)\) comme pour le limiter par le haut.

Exemples. \(1 = O(N), N = O(N^2).\)

Parallèlement aux estimations de la forme \(O(N)\), l'estimation \(\Omega(N)\) (oméga grand) est utilisée. Il désigne la limite inférieure de la croissance de la fonction. Par exemple, supposons que le nombre d'opérations de l'algorithme soit décrit par la fonction \(f(N)=\Omega(N^2)\). Cela signifie que même dans le cas le plus réussi, au moins \(N^2\) actions seront effectuées. Alors que l'estimation \(O(N^3)\) garantit que le pire des cas ne sera rien de plus qu'un ordre \(N^3\) d'actions. L'estimation \(\Theta(N)\) est également utilisée, qui est l'estimation asymptotique supérieure et inférieure lorsque\(Sur et \(\Omega(N)\) sont les mêmes.Ainsi, \(O(N)\) est une estimation approximative de l'algorithme sur les pires données d'entrée,\(\Omega(N)\) - sur les meilleures données d'entrée,\(\Theta(N)\) - notation abrégée pour identique\(O(N)\) et \(\Omega(N)\).

Estimations du temps d'exécution pour différents algorithmes

Notons T(N) comme le temps d'exécution de l'algorithme. Soit l'algorithme étudié sous la forme :

1. un ensemble d'instructions, comprenant uniquement les opérations de base :

Déclaration 1 ;
...
déclaration k ;

Alors T(N) = T(énoncé 1) + ... + T(énoncé k).

Parce que Chaque instruction ne comprend que des opérations de base, alors le temps d'exécution de ce morceau de code ne dépend pas de la taille des données d'entrée (n'augmente pas avec la taille des données d'entrée), c'est-à-dire est une constante. Cet algorithme a une complexité O(1).

2. déclarations if-else

Si (état) (
séquence d'instructions 1
}
autre(
séquence d'instructions 2
}

Ici, soit la séquence d'instructions 1, soit la séquence d'instructions 2 sera exécutée, puisque nous voulons estimer le temps d'exécution dans le pire des cas, T(N) = max(T(séquence d'instructions 1), T(séquence d'instructions 2)). Par exemple, si le temps d'exécution de la séquence d'instructions 1 est O(N) et que la séquence d'instructions est O(1), alors T(N) = O(N).

Pour (i = 0; je< N; i++) {
séquence de déclarations
}

Parce que la boucle sera exécutée N fois, puis la séquence d'instructions sera également exécutée N fois. Si T(séquence d'instructions) = O(1), alors T(N) = O(N)*O(1) = O(N).

4. Boucles imbriquées.

Pour (i = 0; je< N; i++) {
pour (j = 0; j< M; j ++){
...
}
}

La boucle externe est exécutée N fois. Chaque fois que la boucle externe est exécutée, la boucle interne M est exécutée

Considérons maintenant ce code :

Pour (i = 0; je< N; i++) {
pour (j = je + 1; j< N; j ++){
séquence de déclarations
}
}

Regardons l'évolution du nombre d'itérations de la boucle interne en fonction de l'itération de la boucle externe.

Je cycle j (nombre de fois d'exécution)
0N
1N-1
2N-2
...
N-1 1

Ensuite, la séquence d'instructions sera exécutée N + N-1 + ... + 1 fois. Pour calculer rapidement de tels montants, des formules issues d'analyses mathématiques sont utiles, en l'occurrence la formule


Ceux. cet algorithme aura une complexité \(O(N^2)\).

Et voici d’autres formules les plus fréquemment utilisées et utiles dans de tels cas :

4. Lorsqu'une assertion inclut un appel de méthode, l'estimation du temps d'exécution de l'assertion est calculée en tenant compte de l'estimation du temps d'exécution de la méthode. Par exemple:

pour (j = 0; j< N; j ++){


Si le temps d'exécution de la méthode est \(g(N)=O(N)\), alors \(T(N) = O(N)*O(N) = O(N^2)\).

5. Recherche binaire (binaire).

Int l = 0 ;
int u = A.longueur - 1
entier m;
tandis que (l<= u) {
m = l + (u - 1)/2
si A[m]< k {
l = m +1 ;
}
sinon si A[m] == k (
retourner m ;
}
autre(
vous = m - 1 ;
}
}
renvoie -1 ;

La recherche binaire permet de trouver l'index du nombre k dans un tableau trié ; si ce nombre n'y figure pas, alors -1 est renvoyé. Nous comparons d’abord k avec le nombre au milieu du tableau. Si k est inférieur à ce nombre, alors nous devons le rechercher davantage dans la moitié gauche du tableau, si plus, alors dans la moitié droite. Ensuite, k est comparé au nombre situé au milieu de la moitié du tableau sélectionné à l'étape précédente, etc. A chaque itération, l’espace de recherche est réduit de moitié. La question se pose : combien d'itérations faudra-t-il effectuer dans le pire des cas (c'est-à-dire lorsqu'un nombre égal à k n'est jamais trouvé dans le tableau et qu'il ne reste plus de données pour comparaison).

Nous voyons qu'après 1 itération, il restera des données \(N/2\) pour rechercher l'index \(k\), après 2 itérations, il restera des données \(N/4\), après 3 itérations - \( N/8\) et etc. Nous connaîtrons le nombre d'itérations dans le pire des cas si nous résolvons l'équation \(\frac(N)(2^x)=1\). Cette équation est équivalente à l'équation \(2^x=N\), donc \(x=log_(2)(N)\) ou \(x=log(N)\) (voir définition du logarithme). Par conséquent, l’estimation de la complexité de l’algorithme de recherche binaire est \(O(logN)\).

La bonne nouvelle est que pour caractériser le temps d'exécution de la plupart des algorithmes, quelques fonctions suffisent : \(1, logN, N, NlogN, N^2, N^3, 2^N\). Le graphique illustre les différents taux de croissance du temps d'exécution de l'algorithme en fonction de la taille des données d'entrée :

De ce graphique, en particulier, il ressort clairement que si le temps d'exécution de l'algorithme est « logarithmique », c'est-à-dire l'algorithme a une complexité \(O(logN)\), alors c'est très cool, car son temps d'exécution augmente très lentement avec l'augmentation de la taille des données d'entrée, si le temps d'exécution dépend linéairement de la taille des données d'entrée, alors ce n'est pas mal non plus, mais il vaut mieux ne pas utiliser d'algorithmes avec un temps d'exécution exponentiel (\( O(2^N)\)) ou à utiliser uniquement sur de très petites tailles de données.

classes P et NP

Une fonction réelle non négative \(f(m)\), définie pour les valeurs entières positives de l'argument, est dite polynomialement bornée s'il existe un polynôme \(P(m)\) avec des coefficients réels tels que \( f(m) \leq P( m)\) pour tout \(m \in N^+\). Les problèmes pour lesquels il existe des algorithmes à temps d'exécution « polynomial » appartiennent à la classe P (ces problèmes sont pour la plupart résolus rapidement et sans aucun problème).

Définition formelle. Un langage L appartient à la classe P si et seulement s'il existe une machine de Turing déterministe M telle que :

Pour toute donnée d'entrée, M termine son travail en temps polynomial,
- pour tout \(x \in L\) M produit le résultat 1,
- pour tout \(x\) n'appartenant pas à \(L\), M produit le résultat 0.

Problèmes de classe NP- tâches qui satisfont à la condition : s'il y a une réponse (solution possible), alors c'est facile à vérifier - vérifiez si c'est une solution ou non.

Considérons un exemple de problème de la classe NP. Soit par exemple un ensemble d'entiers (-7, -3, -2, 5, 8). Vous devez savoir si parmi ces nombres il y a 3 nombres dont la somme donne 0. Dans ce cas, la réponse est « oui » (par exemple, un tel triplet est constitué des nombres (-3,-2,5). Comme la taille des ensembles d'entiers augmente, le nombre de sous-ensembles, constitués de 3 éléments, augmente de façon exponentielle. Pendant ce temps, si on nous donne un de ces sous-ensembles (on l'appelle aussi certificat), alors nous pouvons facilement vérifier si la somme de ses éléments est égal à 0.

Définition formelle:

Un langage L appartient à la classe NP si et seulement s'il existe des polynômes \(p\) et \(q\) et une machine de Turing déterministe M telle que :

Pour tout \(x,y\), la machine M sur les données d'entrée \((x,y)\) s'exécute en temps \(p(|x|)\),
- pour tout \(x \in L\) il existe une chaîne \(y\) de longueur \(q(|x|)\) telle que \(M(x,y)=1\),
- pour tout \(x\) ne provenant pas de \(L\) et toutes les chaînes de longueur \(q(|x|)\) \(M(x,y)=0\).

Réductibilité polynomiale ou réductibilité de Karp. La fonction \(f_1\) se réduit à la fonction \(f_2\) s'il existe une fonction \(f \in P\) telle que pour tout \(x\) \(f_(1)(x)=f_( 2 )(f(x))\).


Le problème T s’appelle NP-complet, s'il appartient à la classe NP et que tout autre problème de NP peut lui être réduit en temps polynomial. L’exemple le plus célèbre de problème NP-complet est peut-être le problème SAT (du mot satisfiabilité). Donnons une formule contenant des variables booléennes, des opérateurs "ET", "OU", "NON" et des parenthèses. Le problème est : est-il possible d'attribuer des valeurs à toutes les variables apparaissant dans la formule ? mensonge Et vrai pour que la formule prenne la valeur " vrai".

Le problème T s’appelle NP-dur, si pour cela il existe un problème NP-complet qui se réduit à T en temps polynomial. Ce que nous entendons ici, c'est la réductibilité de Cook. La réduction par Cook du problème \(R_1\) à \(R_2\) est un algorithme en temps polynomial qui résout le problème \(R_1\) à condition que la fonction qui trouve la solution au problème \(R_2\) lui soit donnée sous forme d'oracle. , c'est-à-dire que l'accès ne prend qu'une seule étape.

Voici les relations possibles entre les classes de problèmes ci-dessus (les scientifiques ne savent toujours pas si P et NP sont identiques).

ARTICLES LIÉS