算法的时间复杂度

Posted on

时间复杂度

时间复杂度是衡量算法性能的重要标准。

在进行算法分析的时候，我们用 T(n) 来表示语句的执行次数，记作：T(n)= O(f(n))。表示随着问题规模n的增大， 算法的执行时间的增长率和 f(n) 的增长率趋于一致，我们可以选择性地忽略某些项只保留最高次项，我们可以称之为 大O表示法。

举点例子：

O(1)

这样的常数项，T(n) = 100 我们可以总结为 O(1)

1
2
3
count = 0 
for i in range(10):
	count += 1

O(n)

肉眼可见地答案~

1
2
3
count = 0 
for i in range(n):
	count += 1

O(n^2)

T(n) = n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

1
2
3
for i in range(n):
	for j in range(i,n):
		print(i+j)

O(logn)

满足 2^t = n, 即O(logn)

1
2
3
4

while i < n :
	i += 1 
	i = i ** 2

O(nlogn)

1
2
3
4
for n in range(100,10000,1000):
	while i < n :
		i += 1 
		i = i ** 2