算法笔记（七）：复杂度分析（一）

来源：cnblogs　　作者：free赖权华　　时间：2018/10/15 9:26:18　　对本文有异议

（一）渐进符号（这里暂时只考虑大O）

以输入规模n为自变量建立的时间复杂度实际上还是较复杂的，例如an²⁺bn+c+1,不仅与输入规模有关，还与系统a、b和c有关。此时对该函数进一步抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的常量、低阶项、高阶项的系数，仅考虑n²。当输入规模大到只有与运行时间的增长量级有关的时，就是在研究算法的渐进效率。也就是说，从极限角度看，只关心算法运行时间如何随着输入规模的无限增长而增长。

大O记号的定义为：给定一个函数g(n),O(g(n)) = {f(n):存在正常数c和n_0,使得对所有n>=n_0,有0<=f(n)<=cg(n)}.O(g(n))表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上届。

判断下面各式是否成立：

10n²+4n+2 = O(n²) -------- 成立

10n²+4n+2 = O(n) -------- 不成立

（二）示例

1、下面这段代码

1 def F(n):
2     sum = 0
3     i = 0
4     j = 1
5     sun = i + j
6     return sum

上面这段代码的时间复杂度就是O(1)，O(1)表示算法的执行时间总是常量（即1、2、3、4、5....10000行代码的的执行时间都是 O(1)，只要代码的执行次数是常量，它的复杂度就是 O(1)）

2、下面这段代码

1 def F(n):
2     sum = 0
3     for i in range(1,n+1):
4         sum = sum+i
5     return sum

假设第2行代码的执行时间是1,那么3、4行代码都执行了N遍（1、2、3....n），所以代码的执行时间是2n，代码的总执行时间就是2n+1，根据前面的说明，在大O表示法中，我们可以忽略掉公式中的常量、低阶项、高阶项的系数，所以代码的复杂度就是O(n)

3、再看下面这段代码：

1 def F(n):
2     sum = 0
3     for i in range(1,n+1):
4         for j in range(1,n+1):
5             sum = sum+i*j
6     return sum

假设第二行代码执行时间是1，第3行执行时间是n,第4、5行的执行次数都是n²,所以执行时间是2n²。所以代码总的执行时间是T(N) = 1+n+2n²，同理，这段代码的时间复杂度是O(n²)

（三）总结下

总结一下，我们这里遇到下面三种情况

1、O(1) -----常量阶

O(1)表示算法的执行时间总是常量（即1、2、3、4、5....10000行代码的的执行时间都是 O(1)，只要代码的执行次数是确定的，它的执行次数就是 O(1)）

2、O(n) -----线性阶

O(n)表示一个算法的性能会随着输入数据n的大小变化而线性变化

3、O(n²) ----平方阶

O(n²)表示一个算法的性能将会随着输入数据n的增长而呈现出二次增长

另外还有2个没有说的就是对数（O(logN)）和非多项式，非多项式这里不考虑，对数阶算法复杂度分析，下篇说明。

（四）分析插入排序、简单选择排序的算法复杂度

1、插入排序

 1 #插入排序
 2 def insertSort(A):
 3     for i in range(len(A)):
 4         key = A[i]
 5         j = i -1
 6         while A[j] > key and j >=0:
 7             A[j+1] = A[j]
 8             j -= 1
 9         A[j+1] = key
10     return A

（1）假设第3行代码的执行次数是n,那么4、5、9行代码的执行次数也是n，总共4n。

（2）第6、7、8行的执行次数就是n²（最坏的情况），总共是3n²

(3)所以算法的执行次数为 4n+3n²，即时间复杂度为O(n²)

2、简单选择排序

 1 def selectSort(A):
 2     #迭代列表的前n-1个元素
 3     for i in range(len(A)-1):
 4         k = i
 5         for j in range(i+1,len(A)):
 6             if A[k] > A[j]:
 7                 k = j  #更新最小值的索引
 8         #如果A[i]不是最小值，交换A[i],A[k]的值
 9         if k != i:
10             A[k],A[i] = A[i],A[k]
11     return A