时间复杂度示例
1 -基本操作(算术,比较,访问数组元素,赋值):运行时间总是常量O(1)
例子:
read(x) // O(1)
a = 10; // O(1)
a = 1,000,000,000,000,000,000 // O(1)
2 - If then else语句:只从两个或多个可能的语句中获取最大运行时间。
例子:
age = read(x) // (1+1) = 2
if age < 17 then begin // 1
status = "Not allowed!"; // 1
end else begin
status = "Welcome! Please come in"; // 1
visitors = visitors + 1; // 1+1 = 2
end;
因此,上述伪代码的复杂度为T(n) = 2 + 1+ max(1,1 +2) = 6。因此,它的大oh仍然是常数T(n) = O(1)。
3 -循环(for, while, repeat):此语句的运行时间为循环次数乘以循环内的操作次数。
例子:
total = 0; // 1
for i = 1 to n do begin // (1+1)*n = 2n
total = total + i; // (1+1)*n = 2n
end;
writeln(total); // 1
它的复杂度是T(n) = 1+4n+1 = 4n+ 2。因此,T(n) = O(n)。
4 -嵌套循环(循环中循环):由于在主循环中至少有一个循环,这条语句的运行时间使用O(n^2)或O(n^3)。
例子:
for i = 1 to n do begin // (1+1)*n = 2n
for j = 1 to n do begin // (1+1)n*n = 2n^2
x = x + 1; // (1+1)n*n = 2n^2
print(x); // (n*n) = n^2
end;
end;
通用运行时间
在分析算法时,有一些常见的运行时间:
O(1) – Constant time
Constant time means the running time is constant, it’s not affected by the input size.
O(n) – Linear time
When an algorithm accepts n input size, it would perform n operations as well.
O(log n) – Logarithmic time
Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.
O(n log n) – Linearithmic time
This running time is often found in "divide & conquer algorithms" which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm.
O(n2) – Quadratic time
Look Bubble Sort algorithm!
O(n3) – Cubic time
It has the same principle with O(n2).
O(2n) – Exponential time
It is very slow as input get larger, if n = 1,000,000, T(n) would be 21,000,000. Brute Force algorithm has this running time.
O(n!) – Factorial time
The slowest!!! Example: Travelling salesman problem (TSP)
摘自这篇文章。它解释得很好,你应该读一读。