算法复杂度评价一例-阿里云开发者社区

开发者社区> 贺利坚> 正文

算法复杂度评价一例

简介: 问题   数据结构课堂上抛出一个问题,下面一段算法,复杂度是_______? i=1; while(i<=n) i=i*3; A. O(3n)O(3^n) B. O(n)O(n) C. O(n3)O(n^3) D. O(log3n)O(log_3n) 意外   连叫三位同学回答,列一例外选B,让我有些吃惊。看来这是老师的问题,大家的思维没有到位。 分
+关注继续查看

问题
  数据结构课堂上抛出一个问题,下面一段算法,复杂度是_______?

i=1;
while(i<=n)
   i=i*3;

A. O(3n)
B. O(n)
C. O(n3)
D. O(log3n)

意外
  连叫三位同学回答,列一例外选B,让我有些吃惊。看来这是老师的问题,大家的思维没有到位。

分析及解答
  所谓复杂度,是要对关键运算的次数进行计数。关键运算的次数,与问题规模有关。在这里,就是要考察循环了。关键运算是乘法,我们看执行算法中,需要多少次乘法。而问题规模呢?显然,执行多少次循环,与n的初值有关。这里设循环执行的次数为T(n)
  这里循环次数首先可以确定不是B所指定的线性关系。为直观起见,我们设n足够大,用于控制循环的变量 i 的变化过程是:
  1(初值,由i=1
  3(第1次循环:i=i*3
  9(第2次循环:i=i*3
  27(第3次循环:i=i*3
  81(第4次循环:i=i*3
  273(第5次循环:i=i*3
  819(第6次循环:i=i*3
  2457(第7次循环:i=i*3
  ……
  可以看到 i 的值就这样,按着指数级的速度,向着(i<=n)这个使循环结束的条件奔去。
  我们已经设循环执行的次数为T(n)。可以发现,当3T(n)n时,循环继续,循环结束时,恰 3T(n)>n,容易得到 T(n)log3(n),论及复杂度,我们常只考察量级,故有T(n)=O(log3n)

后续的疑问
  课堂中我讲了这个结论得出的过程,大多数同学接受了。个别同学还在继续思考(好习惯,就着热乎劲,有质疑,有思考,学习的优良品质!)。问得最多的问题是:当n=3(或某一个具体的数)时,循环的次数不等于log3n
  对此,暴露出同学们对复杂度的理解中,还有两点不到位:
  1. 复杂度只作粗略的,在定性(量级)上的考察,而不是定量(精确的计数算式)的计算,多几次少几次,不要细究了。注意说复杂度是O(log3n),而不是log3n要深刻理解这儿运用的“大O”的目的。
  2. 复杂度只在意定性,而不在定量,为此,在衡定量级时,只保留高阶部分,低阶部分统计统不管,高阶式子的系数统统去掉。例如,关键运算的执行频度计数为10000n3+200n2+1000,在“取量级”的大方针下,也是O(n3)。因为在 n 值取很大的这个前提下,200n2+1000再大,在n3 面前也别抬头;n3前的系数再大,也不是主要因素。这是复杂度分析中,我们在抓主要矛盾。
  3. 学计算机,计数是个很重要很重要的问题,计数的理论,也是深不可测。精确的计数,感兴趣的同学可以关注,但在算法的复杂度分析上,适应“就到量级”的处理,这里也有大学问,这也是实用的处理。

拓展
(1)下面一段算法,复杂度是_______?

i=n;
while(i>1)
   i=i/3;

A. O(3n)
B. O(n)
C. O(n3)
D. O(log3n)
E. O(1)

(2)下面一段算法,复杂度是_______?

i=1;
while(i<=n)
   i=i+3;

A. O(n/3)
B. O(n)
C. O(3n)
D. O(log3n)

(3)下面一段算法,复杂度是_______?

i=1;
while(i<=n)
   n=i*3;

A. O()
B. O(n)
C. O(3n)
D. O(log3n)

解析
  (1)D。和原问题其实一样,照文章中的思路做一遍即可得到答案。若关键运算执行次数与问题规模n无关时,复杂度为E. O(1),显然,这里 i 的初值是 n ,并非无关。
  (2)B。最迷惑人的,是A。循环的次数,循环次数约是 n3,但是,系数13是要去掉的,选B。
  (3)错题!这段代码若执行,是个死循环,终止于内存溢出,或者有些对溢出不处理的语言,就真的一直会不停地执行下去。从算法角度,由于违反了“有穷性”,这也根本称不上是“算法”了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
常用算法和复杂度总结
一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...
3110 0
算法时间复杂度
算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算不太精确的。只能依据统计方法对算法进行估算。
477 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2200 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4614 0
算法初级笔记(一)认识时间复杂度
声明:本笔记所涉及的资料来源于牛客网 认识时间复杂度 常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作。我的理解是这种操作最终的执行就是执行汇编命令,而汇编命令执行花费的时间都是有限的机器时钟时间,可以简单理解为执行一个相加指令,所以常数操作花费的时间是确定有限的,和数量级没关系。
1018 0
常用算法复杂度速查表,蹲坑的功夫都能背
复杂度通常会使用大 -O记号来表示,比如快速排序的平均时间复杂度是 O(nlog(n))。虽然我们应该做「理解派」,但是即使每个算法/数据结构都理解了,不时仍有可能忘记具体某个算法/数据结构的复杂度(特别是在最好、最坏和平均情形下的复杂度)。因此制作一个 「速查表」 来集中总结是非常有必要的!
761 0
数据结构与算法学习笔记之 复杂度分析
前言:   大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜鸟;需要不断的学习;在学习过程中,经常会有一些自己的看法,和别人独特的见解;我都会一一做好笔记,以便进步; 正文:复杂度分析  一、什么是复杂度分析? 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”,而时间、空间复杂度做为数据结构和算法的精髓,很直观说明了代码”多快“”多省“。
899 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
10784 0
利用Clion对几种排序算法进行时间复杂度与空间复杂度的分析
算法 利用算法解决问题的步骤: 1、将问题模型化 2、找到一个合适的算法 3、这个算法足够快吗?对空间友好吗 4、如果不是,找出为什么 5、找到一个方法解决这个问题 6、一直迭代直到这个问题被解决 ...
981 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
3664 0
+关注
贺利坚
烟台大学计算机学院教师,建设系列学习资源,改革教学方法,为IT菜鸟建跑道,让大一的孩子会编程,为迷茫的大学生出主意,一起追求快乐的大学。 著书《逆袭大学:传给IT学子的正能量》,帮助处于迷茫中的大学
1942
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载