基础

假设你要画一个包含16个格子的网格。

image.png

• １．一次画一个

一种方法是以每次画一个的方式画16个格子。记住,大O表示法计算的
是操作数。在这个示例中,画一个格子是一次操作,需要画16个格子。
如果每次画一个格子,需要执行多少次操作呢?

image.png

• ２．对折

你每折一次,绘制出的格子数都翻倍,因此4步就能“绘制”出16个格
子。这种算法的运行时间是多少呢?请搞清楚这两种算法的运行时间之
后,再接着往下读。

• 结论

算法1的运行时间为O (n ),算法2的运行时间为O (log n )。

image.png

常见查找算法

• O (log n ),也叫对数时间 ,这样的算法包括二分查找。
• O (n ),也叫线性时间 ,这样的算法包括简单查找。
• O (n * log n ),这样的算法包括快速排序——一种速度较快的排序算法。
• O (n 2 ),这样的算法包括选择排序——一种速度较慢的排序算法。
• O (n !) 一种非常慢的算法。

算法的速度指的并非时间,而是操作数的增速。谈论算法的速度时,我们说的是随着输入的增加,其运行时间将以什么样的速度增加。算法的运行时间用大O表示法表示。O (log n )比O (n )快,当需要搜索的元素越多时,前者比后者快得越多。

demo.png

参考资料

• 本文最新版本地址
• 本文涉及的python测试开发库 谢谢点赞！
• 本文相关海量书籍下载
• python工具书籍下载-持续更新
• 本文代码
• 本文配套视频在线播放 下载

旅行商算法简介

有一位旅行商。他需要前往5个城市。

image.png

这位旅行商(姑且称之为Opus吧)要前往这5个城市,同时要确保旅程
最短。为此,可考虑前往这些城市的各种可能顺序。

image.png

推而广之,涉及n 个城市时,需要执行n !(n 的阶乘)次操作才能计算出结果。因此运行时间为O (n !),即阶乘时间。除非涉及的城市数很少,否则需要执行非常多的操作。如果涉及的城市数超过100,根本就不能在合理的时间内计算出结果——等你计算出结果,太阳都没了。

这种算法很糟糕!Opus应使用别的算法,可他别无选择。这是计算机科学领域待解的问题之一。对于这个问题,目前还没有找到更快的算法,有些很聪明的人认为这个问题根本就没有更巧妙的算法。面对这个问题,我们能做的只是去找出近似答案,更详细的信息请参阅第10章。

练习: 用python列表实现二分查找法

此题为shopee(虾皮) 面试题，要求用非递归算法实现。代码参见参考资料中的本文代码：

https://github.com/china-testing/python-testing-examples/tree/master/interview

建议拷贝上述网址到浏览器访问。

binary_search1.py binary_search2.py

参考答案

image.png

原著是一个有趣的人,若有侵权,请通知删除