时间复杂度的规则与计算 - 好文

1. 分析算法时，存在几种可能的考虑：

* 算法完成工作最少需要多少基本操作，即最优时间复杂度
* 算法完成工作最多需要多少基本操作，即最坏时间复杂度
* 算法完成工作平均需要多少基本操作，即平均时间复杂度
对于最优时间复杂度，其价值不大，因为它没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。

对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。

对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。

因此，我们主要关注算法的最坏情况，亦即最坏时间复杂度。

2. 时间复杂度的几条基本计算规则

* 基本操作，即只有常数项，认为其时间复杂度为O(1)
* 顺序结构，时间复杂度按加法进行计算
* 循环结构，时间复杂度按乘法进行计算
* 分支结构，时间复杂度取最大值
* 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
* 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度
3. 常见时间复杂度

执行次数函数举例阶非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n2+2n+1 O(n2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlogn阶
6n3+2n2+3n+4 O(n3) 立方阶
2n O(2n) 指数阶
注意，经常将log2n（以2为底的对数）简写成logn

4. 常见时间复杂度之间的关系

所消耗的时间从小到大

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

5. 例题:

题: 如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?

法1:
#coding=utf-8 import time #开始时间 start_time = time.ctime(); print("start time:
%s" %start_time) for i in range(0, 1001): # 复杂度 n for j in range(0, 1001): #
复杂度 n*n for k in range(0, 1001): # 复杂度 n*n*n(max(1, 0)) = n^3 if i+j+k==1000
and i**2+j**2==k**2: print("i-j-k: %d-%d-%d" %(i,j,k)) #结束时间 end_time =
time.ctime() print("end_time: %s" %end_time) #所以最坏时间复杂度为 # T(n) = n*n*n(max(1,
0)) = n^3

法2:
#coding=utf-8 import time start_time = time.ctime(); print("start time: %s"
%start_time) for i in range(0, 1001): # 复杂度 n for j in range(0, 1001): # 复杂度
n*n k = 1000-i-j # 复杂度 n*n*(1+max(1, 0)) if i**2+j**2==k**2: print("i-j-k:
%d-%d-%d" % (i, j, k)) end_time = time.ctime() print("end_time: %s" %end_time)
#最坏时间复杂度 # T(n) = n*n*(1+ max(1, 0)) = n^2*2 = O(n^2)

法1(n^3) 和法2(n^2) 两者执行时间相差很大, 所以一个好的时间复杂度的程序对于程序效率的提升是很好的!

热门工具换一换