首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法笔记(七):复杂度分析(一)

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

作者头像
free赖权华
发布2018-10-15 13:07:30
5530
发布2018-10-15 13:07:30
举报
文章被收录于专栏:赖权华的笔记赖权华的笔记

(一)渐进符号(这里暂时只考虑大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)

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-10-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档