Que comprend principalement la complexité des algorithmes ?

Complexité algorithmique :

Complexité temporelle

En informatique, complexité temporelle, également appelée complexité temporelle Degré, le La complexité temporelle d'un algorithme est une fonction qui décrit qualitativement le temps d'exécution de l'algorithme. Ceci est fonction de la longueur de la chaîne représentant la valeur d'entrée de l'algorithme. La complexité temporelle est souvent exprimée en notation grand O, à l'exclusion des termes d'ordre inférieur et des coefficients principaux de cette fonction. Lorsque vous utilisez cette approche, la complexité temporelle peut être considérée comme asymptotique, c'est-à-dire que la taille des valeurs d'entrée s'approche de l'infini.

Afin de calculer la complexité temporelle, nous estimons généralement le nombre d'unités d'opération de l'algorithme, et le temps d'exécution de chaque unité est le même. Par conséquent, la durée totale d’exécution et le nombre d’unités opérationnelles de l’algorithme diffèrent au maximum d’un facteur constant.

Différentes valeurs d'entrée de même taille peuvent toujours entraîner une différence dans le temps d'exécution de l'algorithme, nous utilisons donc généralement la complexité la plus défavorable de l'algorithme, notée T(n), qui est défini comme le temps requis pour l'entrée n de n'importe quelle taille. Durée d'exécution maximale. Une autre méthode moins couramment utilisée est la complexité moyenne des cas, qui n'est généralement utilisée que lorsque cela est spécifié. La complexité temporelle peut être classée selon les caractéristiques naturelles de la fonction T(n). Par exemple, un algorithme avec T(n) =O(n) est appelé « algorithme de temps linéaire » tandis que T(n) =O(M) ; ^n) et M= O(T(n)), l'algorithme où M≥n> 1 est appelé « algorithme de temps exponentiel ».

Le temps que prend un algorithme est proportionnel au nombre d'exécutions d'instructions dans l'algorithme. Quel que soit l'algorithme qui a le plus d'instructions exécuté, cela prend plus de temps. Le nombre d’exécutions d’instructions dans un algorithme est appelé fréquence d’instruction ou fréquence temporelle. Notons-le comme T(n).
De manière générale, le nombre d'exécutions répétées d'opérations de base dans un algorithme est fonction de la taille du problème n, représentée par T(n). S'il existe une fonction auxiliaire f(n), lorsque n tend vers l'infini, la la valeur limite de T(n)/f(n) est une constante non égale à zéro, alors f(n) est dit être une fonction du même ordre de grandeur que T(n). Notée T(n)=O(f(n)), O(f(n)) est appelée la complexité temporelle asymptotique de l'algorithme, ou complexité temporelle en abrégé.
Dans divers algorithmes, si le nombre d'exécutions d'instructions dans l'algorithme est constant, la complexité temporelle est O(1). De plus, lorsque la fréquence temporelle est différente, la complexité temporelle peut être la même, comme T. ( n)=n2+3n+4 et T(n)=4n2+2n+1 ont des fréquences différentes, mais la complexité temporelle est la même, les deux sont O(n2).

Temps Fréquence

Le temps nécessaire à l'exécution d'un algorithme ne peut pas être calculé théoriquement. Il ne peut être connu qu'en exécutant un test sur l'ordinateur. Mais il est impossible et inutile pour nous de tester chaque algorithme sur l’ordinateur. Il nous suffit de savoir quel algorithme prend le plus de temps et quel algorithme prend le moins de temps. Et le temps nécessaire à un algorithme est proportionnel au nombre d’exécutions d’instructions dans l’algorithme. Quel que soit l’algorithme qui a le plus d’instructions exécutées, cela prend plus de temps. Le nombre d’exécutions d’instructions dans un algorithme est appelé fréquence d’instruction ou fréquence temporelle. Notons-le comme T(n).

Complexité spatiale

Semblable à la complexité temporelle, la complexité spatiale fait référence à la mesure de l'espace de stockage requis lorsqu'un algorithme est exécuté dans un ordinateur. Enregistré sous la forme :

S(n)=O(f(n))

L'espace de stockage requis lors de l'exécution de l'algorithme comprend 3 parties :

• L'espace occupé par le programme d'algorithme ;

• L'espace de stockage occupé par la saisie de données initiale

• Requis lors de l'exécution de l'algorithme Extra ; espace.

Dans de nombreux problèmes pratiques, afin de réduire l'espace de stockage occupé par l'algorithme, la technologie de stockage par compression est généralement utilisée.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!