算法笔记(七):复杂度分析(一)

2018-10-14 10:50:24来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

(一)渐进符号(这里暂时只考虑大O)

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

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

 判断下面各式是否成立:

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

10n2+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行的执行次数都是n2,所以执行时间是2n2。所以代码总的执行时间是T(N) = 1+n+2n2,同理,这段代码的时间复杂度是O(n2)

(三)总结下

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

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

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

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

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

3、O(n2)  ----平方阶 

O(n2)表示一个算法的性能将会随着输入数据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行的执行次数就是n2(最坏的情况),总共是3n2

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

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

一样的道理,我们只需要关注代码执行次数最多的那段代码就行了,即第5行代码(n2),所以算法的时间复杂度也是O(n2)

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:appium+python环境搭建

下一篇:第11天内置函数详解