算法图解——读书笔记01

二分查找

通过一个简单的例子说明二分查找的工作原理。我随便想一个1~100的数字。

你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
假设你从1开始一次往上猜，猜测过程会是这样。

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到！
更佳的查找方式

下面是一种更佳的猜法。从50开始。
小了，但是排除了一半 的数字！至此，你知道1-50都小了，接下来，你猜75。

大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63（50和75中间的数字。）

这就是二分查找！每次猜测排除的数字个数如下：

不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！
一般而言，对于包含N个元素的列表，用二分查找最多需要log₂n步，而简单查找最多需要n步。

但是二分查找仅当列表有序的时候，二分查找才管用

大O表示法

举个栗子：
Bob使用包含10亿个元素的列表运行二分查找，运行时间为30毫秒（log21000000000大约为30）。他心里想，二分查找的速度大约为简单查找的15倍，因为列表包含100个元素时，简单查找需要100毫秒，而二分查找需要7毫秒。因此，列表包含10亿个元素时，简单查找需要30×15=450毫秒，完全符合在10秒内查找完毕的要求。Bob决定使用简单查找。这是正确的选择吗？

不是，实际上，Bob错了，而且错的离谱。列表包含10亿个元素时，简单查找需要10亿毫秒，相当于11天！！！为什么会这样呢？因为二分查找和简单查找的运行时间的增速不同。

也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多，因此，随着列表的增长，二分查找的速度比简单查找快的多。Bob以为二分查找速度为简单查找的15倍U，这不对：列表包含10亿个元素时，为3300万倍。有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)。单位秒呢？没有——大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。
一些常见的大O运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
❑ O(log n)，也叫对数时间，这样的算法包括二分查找。
❑ O(n)，也叫线性时间，这样的算法包括简单查找。
❑ O(n ＊ log n)，这样的算法包括快速排序—— 一种速度较快的排序算法。
❑ O(n2)，这样的算法包括选择排序—— 一种速度较慢的排序算法。
❑ O(n! )，这样的算法包括旅行商问题的解决方案—— 一种非常慢的算法。

下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间：

总结：

❑ 二分查找的速度比简单查找快得多。
❑ 算法的速度指的并非时间，而是操作数的增速。
❑ 算法运行时间并不以秒为单位。
❑ 算法运行时间是从其增速的角度度量的。
❑ 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
❑ 算法的运行时间用大O表示法表示。
❑ O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。