Comment mesurer l’efficacité du temps d’exécution d’un algorithme ?

En ignorant les performances de la machine, nous utilisons la complexité temporelle de l'algorithme pour mesurer le temps d'exécution de l'algorithme.
1. Fréquence temporelle
Le temps nécessaire à l'exécution d'un algorithme ne peut pas être calculé théoriquement. Vous devez exécuter un test sur un ordinateur pour le connaître. 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. EtLe 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).
2. 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é.

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 comprennent :
Ordre constant O(1), ordre logarithmique O(log2n) (logarithme de n avec 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è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.
Analyse des performances temporelles de l'algorithme
(1) Temps passé par l'algorithme et fréquence des instructions

Temps passé par un algorithme = somme du temps d'exécution de chaque instruction dans l'algorithme

Le temps d'exécution de chaque instruction = le nombre d'exécutions de l'instruction (c'est-à-dire la fréquence (Frequency Count)) × le temps nécessaire pour exécuter l'instruction une fois

Une fois l'algorithme converti en programme, le temps requis pour exécuter chaque instruction dépend de facteurs difficiles à déterminer, tels que les performances des instructions de la machine, la vitesse et la qualité du code généré par la compilation.

Pour analyser la consommation de temps d'un algorithme indépendamment des systèmes logiciels et matériels de la machine, supposons que le temps requis pour exécuter chaque instruction une fois est un temps unitaire et que la consommation de temps d'un algorithme correspond à toutes les instructions du algorithme. La somme des fréquences.
Pour trouver le produit C=A×B de deux matrices carrées d'ordre n, l'algorithme est le suivant :

　　# define n 100 // n 可根据需要定义,这里假定为100
　　void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
　　{ //右边列为各语句的频度
　　int i ,j ,k;
　　 for(i=0; i<n;j++) n+1
　　 for (j=0;j<n;j++) { n(n+1)
　　 C[i][j]=0; n
　　 for (k=0; k<n; k++) nn(n+1)
　　 C[i][j]=C[i][j]+A[i][k]*B[k][j];n
　　}
　　}

La somme des fréquences de toutes les instructions de l'algorithme (c'est-à-dire le temps de l'algorithme Coût) est :

T(n)=nn(n+1) (1.1)

Analyse :

La variable de contrôle de boucle i de l'instruction (1) doit être augmenté à n, le test ne se terminera que lorsque i=n sera établi. Sa fréquence est donc n+1. Mais son corps de boucle ne peut être exécuté que n fois. L'instruction (2), en tant qu'instruction dans le corps de la boucle de l'instruction (1), doit être exécutée n fois, mais l'instruction (2) elle-même doit être exécutée n+1 fois, donc la fréquence de l'instruction (2) est n( n+1). De la même manière, les fréquences des phrases (3), (4) et (5) sont respectivement n, nn(n+1) et n.

La consommation de temps T(n) de l'algorithme MatrixMultiply est fonction de l'ordre matriciel n3.

(2) Échelle du problème et complexité temporelle de l'algorithme
La quantité d'entrée de l'algorithme pour résoudre le problème est appelée la taille du problème (Taille), qui est généralement représentée par un nombre entier.

L'échelle du problème du produit matriciel est l'ordre de la matrice.

La taille d'un problème de théorie des graphes est le nombre de sommets ou d'arêtes dans le graphique.

La complexité temporelle (Time Complexity, aussi appelée complexité temporelle) T(n) d'un algorithme est la consommation de temps de l'algorithme et est fonction de la taille n du problème résolu par l'algorithme. Lorsque la taille du problème n tend vers l’infini, l’ordre de grandeur (ordre) de la complexité temporelle T(n) est appelé complexité temporelle asymptotique de l’algorithme.

La complexité temporelle T(n) de l'algorithme MatrixMultidy est représentée dans l'équation (1.1). Lorsque n tend vers l'infini, il y a évidemment T(n)~O(n3);

Cela montre que lorsque n est suffisamment grand, le rapport de T(n) et n3 est une constante non égale à zéro. Autrement dit, T(n) et n3 sont du même ordre, ou T(n) et n3 sont du même ordre de grandeur. Notée T(n)=O(n3), c'est la complexité temporelle asymptotique de l'algorithme MatrixMultiply.

(3) La complexité temporelle asymptotique évalue les performances temporelles d'un algorithme

Utilise principalement l'ordre de grandeur de la complexité temporelle de l'algorithme (c'est-à-dire la complexité temporelle asymptotique de l'algorithme) pour évaluer la performance temporelle d’un algorithme.
La complexité temporelle de l'algorithme MatrixMultiply est généralement T(n)=O(n3), et f(n)=n3 est la fréquence de l'instruction (5) dans l'algorithme. Ensuite, nous donnerons un exemple pour illustrer comment trouver la complexité temporelle de l'algorithme.

Échangez le contenu de i et j.

Temp=i;
i=j;
j=temp;

　　以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。　　
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：

　　 x=0;y=0;
　　 for(k-1;k<=n;k++)
　　 x++;
　　 for(i=1;i<=n;i++)
　　 for(j=1;j<=n;j++)
　　 y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

变量计数之二：

x=1;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

在数值A[0..n-1]中查找给定值K的算法大致如下：

i=n-1;
while(i>=0&&(A[i]!=k))
 i--;
return i;

此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:

①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；

②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

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!