编程导论-算法复杂度简介

节后第一篇,友情提醒,本微信公众号,QQ群号,还有CSDN博客,三位一体,名字都叫(Mark学编程),Mark乃老编英文名字。本微信公众号,目前每天推送一篇Python教程文章,同名QQ群以互动交流为主,大量教程及相关编程资料供下载,CSDN同名博客也有大体相同的文章展示

照旧,节前的小测试参考答案如下:

注意:“ ”中间是有空格的,如果在你编写代码有困难或运行结果与预期差异较大,要善于使用type()观察代码返回类型,比如,你忘记了input会返回什么类型,那就type一下吧,或者干脆help()查阅一番, 有时候,或者大部分时候,如果程序有问题,就在问题周边用print来看看有什么输出。这些都是经验之谈,请多多实践。

下面是今天的小测试,英文较差者,直接略过,看中文大体解释:

Question11

Level2

Question:

Write a program which accepts a sequence of comma separated4digit binary numbersasitsinputandthen check whether they are divisible by5ornot.The numbers that are divisible by5are to be printedina comma separated sequence.

Example:

0100,0011,1010,1001

Then the output should be:

1010

Notes:Assumethe dataisinputby console.

编写一程序,接受逗号分隔的4位二进制数字若干,然后检查其是否被5整除,能被5整除的打印出来。请参看上面的例子。

What? you不懂二进制,号内群内严重警告!你需要抓紧找些资料看看,你不需要精通它,但你至少要了解它。

言归正传,今天我们讨论(编程导论)的第九章 算法复杂度简介

这本书的这一章,一下子将其区别于普通的Python编程教材或注重语法的书籍,不亏是MIT的教授,作者专门就此简介了一番,使得本书立即高大上了。窃以为,懂不懂算法复杂度也是专业人士与业余编程的区别之一。所以,在经过一番权衡之后,老编还是顺从本书的次序,决定作为开春第一课的。

代码能够出现预期的准备结果,自然是最最重要的,但是,性能,比如运行速度也是关键因素,比如,代码驱动的飞机飞行,你能够准确预警前方的障碍物,但你报警时间太迟,那也是万万无法接受的。

如果你知道,去年,当报考艺术院校的学子们,几经操作,无法登陆报考APP,或者登陆不久,程序频频崩溃时,你是怎样一个心情?新闻上说,好多艺考生,在频遭程序崩溃的折磨后,直接跪倒了手机屏幕前,如果,你是这个APP的代码设计者,相信早已被众多艺考生们的骂声所惊醒。是呀,编写高效的程序并不容易,最简单的算法往往并不高效,高效的算法通常会使用很难理解的技巧。要想降低计算的复杂度,提高效率,首先要知道代码的复杂度。因此,评估一个程序的计算复杂度成为编写高效算法的基础。

1. 思考计算复杂度

请看下面的代码,并尝试回答,下面的函数会运行多长时间?

我们当然可以输入一些数据,然后运行并测试其运行时间,但是:

1)运行程序的电脑性能会导致不同运行时间;

2)你运行的这台电脑上的Python性能不同会导致不同的运行时间;

3)输入的值不同,会导致不同的运行时间;

我们不用捉急,先辈们已经使用了一个叫做“一步”的抽象概念来解决这个问题了。如果简单理解,一步就是计算的一个操作。

我们再看下面的程序:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190209G0H8FP00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励