On the basis of ignoring machine performance, we use algorithm time complexity to measure the execution time of the algorithm.
1. Time frequency
The time it takes to execute an algorithm cannot be calculated theoretically. It can only be known by running a test on the computer. But it is impossible and unnecessary for us to test every algorithm on the computer. We only need to know which algorithm takes more time and which algorithm takes less time. And The time an algorithm takes is proportional to the number of executions of statements in the algorithm. Which algorithm has more statements, the more time it takes. The number of statement executions in an algorithm is called statement frequency or time frequency. Denote it as T(n).
2. Time complexity
In the time frequency just mentioned, n is called the scale of the problem. When n keeps changing, the time frequency T(n) will also keep changing. But sometimes we want to know what pattern it shows when it changes. To this end, we introduce the concept of time complexity.
Generally, the number of times the basic operations in the algorithm are repeated is a function of the problem size n, represented by T(n). If there is an auxiliary function f(n), such that when n approaches At infinity, the limit value of T(n)/f(n) is a constant not equal to zero, then f(n) is said to be a function of the same order of magnitude as T(n). Denoted as T(n)=O(f(n)), O(f(n)) is called the asymptotic time complexity of the algorithm, or time complexity for short.
In various algorithms, if the number of statement executions in the algorithm is a constant, the time complexity is O(1). In addition, when the time frequency is different, the time complexity may be the same. For example, T(n)=n^2 3n 4 and T(n)=4n^2 2n 1 have different frequencies, but the time complexity is the same, both are O(n^2).
Arranged in increasing order of magnitude, common time complexity is:
Constant order O(1), logarithmic order O(log2n) (logarithm of n with base 2, the same below), linear order O( n),
Linear logarithmic order O(nlog2n), square order O(n^2), cubic order O(n^3),...,
kth power order O(n^k) , exponential order O(2^n). As the problem size n continues to increase, the above time complexity continues to increase, and the execution efficiency of the algorithm becomes lower.
Time performance analysis of the algorithm
(1) Time spent by the algorithm and statement frequency
The time spent by an algorithm = the sum of the execution time of each statement in the algorithm
The execution time of each statement = the number of executions of the statement (ie, frequency (Frequency Count)) × the time required to execute the statement once
After the algorithm is converted into a program, the time required to execute each statement depends on It depends on factors that are difficult to determine, such as the machine's instruction performance, speed, and the quality of the code generated by compilation.
To analyze the time consumption of an algorithm independently of the machine's software and hardware systems, assume that the time required to execute each statement once is unit time, and the time consumption of an algorithm is all the statements in the algorithm. The sum of frequencies.
To find the product C=A×B of two n-order square matrices, the algorithm is as follows:
# 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
}
}The sum of the frequencies of all statements in the algorithm (that is, the time of the algorithm Cost) is:
T(n)=nn(n 1) (1.1)
Analysis:
The loop control variable i of statement (1) should be increased to n , the test will not terminate until i=n is established. Therefore its frequency is n 1. But its loop body can only be executed n times. Statement (2), as a statement within the loop body of statement (1), should be executed n times, but statement (2) itself must be executed n 1 times, so the frequency of statement (2) is n(n 1). In the same way, the frequencies of sentences (3), (4) and (5) are n, nn(n 1) and n respectively.
The time consumption T(n) of the algorithm MatrixMultiply is a function of the matrix order n3.
(2) Problem scale and algorithm time complexity
The input amount of the algorithm to solve the problem is called the size of the problem (Size), which is generally represented by an integer.
The scale of the matrix product problem is the order of the matrix.
The size of a graph theory problem is the number of vertices or edges in the graph.
The time complexity (Time Complexity, also called time complexity) T(n) of an algorithm is the time consumption of the algorithm and is a function of the size n of the problem solved by the algorithm. When the size of the problem n approaches infinity, the order of magnitude (order) of the time complexity T(n) is called the asymptotic time complexity of the algorithm.
The time complexity T(n) of the algorithm MatrixMultidy is shown in equation (1.1). When n tends to infinity, there is obviously T(n)~O(n3);
This shows that , when n is large enough, the ratio of T(n) and n3 is a constant not equal to zero. That is, T(n) and n3 are of the same order, or T(n) and n3 are of the same order of magnitude. Denoted as T(n)=O(n3), it is the asymptotic time complexity of the algorithm MatrixMultiply.
(3) Asymptotic time complexity evaluation algorithm time performance
Mainly use the order of magnitude of algorithm time complexity (that is, the asymptotic time complexity of the algorithm) to evaluate the time performance of an algorithm.
The time complexity of the algorithm MatrixMultiply is generally T(n)=O(n3), and f(n)=n3 is the frequency of statement (5) in the algorithm. Next, we will give an example to illustrate how to find the time complexity of the algorithm.
Exchange the contents of i and 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。
The above is the detailed content of How to measure the execution time efficiency of an algorithm?. For more information, please follow other related articles on the PHP Chinese website!