La complexité temporelle et la complexité spatiale de l'algorithme

La complexité de l'algorithme fait référence aux ressources nécessaires pour exécuter l'algorithme après son écriture dans un programme exécutable. Les ressources incluent les ressources de temps et les ressources de mémoire. Applications à l'introduction aux mathématiques et à l'informatique.

Définition de la complexité temporelle de l'algorithme : (Apprentissage recommandé : Tutoriel vidéo PHP)

En cours Pendant analyse d'algorithme, le nombre total d'exécutions d'instructions T(n) est fonction de la taille du problème n, puis le changement de T(n) avec n est analysé et l'ordre de grandeur de T(n) est déterminé. La complexité temporelle de l'algorithme, c'est-à-dire la mesure temporelle de l'algorithme, s'écrit : T(n) = O(f(n)). Cela signifie qu'à mesure que la taille du problème n augmente, le taux de croissance du temps d'exécution de l'algorithme est le même que le taux de croissance de f(n), appelé complexité temporelle asymptotique de l'algorithme, également appelé complexité temporelle. où f(n) est fonction de la taille du problème n.

Utilisez O() majuscule pour refléter la complexité temporelle de l'algorithme, que nous appelons la notation Big O.

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. Par exemple, T(n)=n^2+3n+4 et T(n)=4n^2+2n+1 ont des fréquences différentes, mais la complexité temporelle est la même, les deux sont O(n^2).

Disposées par ordre de grandeur croissant, les complexités temporelles courantes sont :

Ordre constant O(1), ordre du logarithme O(log2n) (logarithme de n en base 2, le même ci-dessous) ) , ordre linéaire O(n),

ordre logarithmique linéaire O(nlog2n), ordre carré O(n^2), ordre cubique O(n^3),...,

K-ième ordre de puissance O(n^k), ordre exponentiel O(2^n). À mesure que la taille du problème n continue d’augmenter, la complexité temporelle ci-dessus continue d’augmenter et l’efficacité d’exécution de l’algorithme diminue.

Complexité spatiale des algorithmes

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.

est enregistré comme :

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

L'espace supplémentaire requis lors de l'exécution de l'algorithme ;

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.

Pour plus d'articles techniques liés à PHP, veuillez visiter la colonne Tutoriel graphique PHP pour apprendre

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!