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

节后第一篇，友情提醒，本微信公众号，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）输入的值不同，会导致不同的运行时间；

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

我们再看下面的程序：