La complexité temporelle de l'algorithme est

La complexité temporelle d'un algorithme fait référence au nombre d'opérations de base requises lors de l'exécution de l'algorithme.

Un algorithme est un ensemble de règles bien définies utilisées pour résoudre un problème en un nombre limité d'étapes. (Apprentissage recommandé : Tutoriel vidéo MySQL)

En termes simples, il s'agit du processus de résolution de problèmes informatiques. La complexité d'un algorithme est une mesure de l'efficacité de l'algorithme, de la quantité de ressources informatiques requises pour exécuter l'algorithme et une base importante pour évaluer la qualité de l'algorithme. Nous pouvons évaluer la qualité d’un algorithme en fonction de sa complexité temporelle et spatiale.

Lorsqu'un algorithme est converti en programme et exécuté sur un ordinateur, le temps nécessaire à son exécution dépend des facteurs suivants :

(1) La vitesse du matériel.

(2) Langage pour écrire des programmes. Plus le niveau du langage d’implémentation est élevé, moins son exécution est efficace.

(3) La qualité du code objet généré par le compilateur. Les compilateurs avec une meilleure optimisation du code produiront des programmes de meilleure qualité.

(4) Ampleur du problème. Par exemple, le temps d'exécution pour trouver des nombres premiers inférieurs à 100 et trouver des nombres premiers inférieurs à 1000 doit être différent.

Évidemment, il est difficile de comparer le temps d'exécution des algorithmes lorsque divers facteurs sont incertains. Autrement dit, il n’est pas approprié de mesurer l’efficacité d’un algorithme en utilisant le temps absolu nécessaire à son exécution. Par conséquent, la complexité temporelle ne peut pas être déterminée par le temps d'exécution ou la longueur du programme d'algorithme, mais doit être mesurée par le nombre d'opérations de base requises lors de l'exécution de l'algorithme. Fréquence de temps 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 temporelle. Notons-le comme T(n).

Complexité temporelle

Dans la fréquence temporelle que nous venons de mentionner, n est appelé l'ampleur du problème. Lorsque n continue de changer, la fréquence temporelle T(n) continuera également de changer. Mais parfois, nous voulons savoir quel modèle cela montre lorsqu’il change. Pour cela, nous introduisons la notion de complexité temporelle. Généralement, 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), telle que lorsque n. approches A l'infini, la valeur limite de T(n)/f(n) est une constante non égale à zéro, alors f(n) est dit 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é.

Pour plus d'articles techniques liés à MySQL, veuillez visiter la colonne

Tutoriel MySQL

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!