年底了！！！过了一年的“总结”日子：日报总结、周报总结、月报总结。。在一年收尾之前也想把看过的算法总结一下，算是过一个完整的“总结”年。
算法是一组完成任务的指令。任何代码片段都可视为算法。算法很无聊，但也有很有趣的的部分。我们也可以用速度比较快的算法来解决有趣的问题。比如：我们先讨论二分查找，并演示算法如何能够提高代码的速度。在一个示例中，算法将需要 8 执行的步骤从40亿个减少到了32个!
tips : 这篇文章中使用的实例是用Python演示的。
（1）二分查找
实例引入：
当我们在客户端登录淘宝账户时，淘宝肯定是要核实你是否用其网站的账户，因此必须在数据库中查找你的用户名。如果你的用户名为 Kobe Bryant ，你认为淘宝会怎么查找你的账户呢？从 A 开始查找？显然不是。正常的逻辑是从中间开始查找。
这个一个简单的查找问题，我们完全可以用一种算法来解决问题，这中算法就是 二分查找。
二分查找是一种算法，其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要 查找的元素包含在列表中，二分查找返回其位置;否则返回null。
通过一个简单的例子来说明一下二分查找的原理。
我随机在 1---100 之间猜一个数字，你的目标就是以最少的次数猜到我选的数字。
建设你从1开始猜，那么猜的过程绝对美得不敢想象。。。。如果我选的数是99，岂不要猜到猴年马玉去了。这是简单查找，更准确的说是傻找。那么更佳的查找方式是哪种呢？？？
（1.1）更佳的查找方式
先从50开始猜，如果我说小了。一次就排除了一半的数字。
再猜75，如果我说大了。一次又排除一半的数字。
接下来再猜63，依次排除。
...
...
...
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次 猜测都将排除很多数字!
这不是偶然！其中是有一定的规律：
一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步
而简单查找最多需要n步
对数和幂
你可能不记得什么是对数了，但很可能记得什么是幂。log10100相当于问“将多少个10相乘 的结果为100”。答案是两个:10 × 10 = 100。因此，log10100 = 2。对数运算是幂运算的逆运算。
接下来用Python代码编写一个 二分查找
该代码的实现：给定数组、元素，找到这个元素在数组中的下标。
def binary_search(list, item):
# 声明最低的下标和最高的下标
low = 0
high = len(list)-1
while low <= high:
# 首先获取中间值下标
# 如果(low + high)不是偶数， Python自动将mid向下圆整。
mid = (low + high)/2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None
# 测试
my_list = [1, 3, 5, 7, 9]
print (binary_search(my_list, 5))
#
print (binary_search(my_list, 10))
（1.2）运行时间
算法可以帮我们大大减少繁琐的步骤，但是不同的算法之间还是有“优良之分”的，这点从运行时间上可以做一下比较。
回到前面的二分查找。使用它可节省多少时间呢?简单查找逐个地检查数 字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最 多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为 线性 时间(linear time)。
二分查找则不同。如果列表包含100个元素，最多要猜7次;如果列表包含40亿个数字，最多 需猜32次。厉害吧?二分查找的运行时间为对数时间(或log时间)。下表总结了我们发现的情况
（1.3）大O表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快。谁在乎呢?实际上，你经常要 使用别人编写的算法，在这种情况下，知道这些算法的速度大有裨益。
（1.3.1）算法的运行时间以不同的速度增加
我们先来假设查找一个元素用 1 毫秒。使用简单查找时，检查100个元素，因此需要100毫秒 才能查找完毕。而使用二分查找时，只需检查7个元素(log2100大约为7)，因此需要7毫秒就能查 找完毕。然而，如果要查找的列表可能包含10亿个元素，在这种情况下，简单查找需要多长时间 呢?二分查找又需要多长时间呢?
能不能这么认为呢？查找100个元素，简单查找是二分查找的 15 倍的时间。当查找 10 个元素的时候，时间也保持这个倍数关系？
假如上述假设成立，10亿个元素的列表运行二分查找，运行时间为30毫秒(log21 000 000 000大约为 30)，那么简单查找用时应该为450毫秒。事实却不是这样，简单查找需要 10亿 毫秒。
为什么会用那么大的差距？因为 简单查找 与 二分查找 的增速不同。有鉴于此，仅知道算法 需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长 而增加。
大O表示法指出了算法有多快。例如，假设列表包含n个元素。简 单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法， 这个运行时间为O(n)。单位秒呢?没有——大O表示法指的并非以秒为单位的速度。大O表示法 让你能够比较操作数，它指出了算法运行时间的增速。
（1.3.2）一些常见的大O运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
- O(log n)，也叫对数时间，这样的算法包括二分查找。
- O(n)，也叫线性时间，这样的算法包括简单查找。
- O(n * log n)，这样的算法常见一种速度较快的排序算法。
- O(n2)，这样的算法常见一种速度较慢的排序算法。
- O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
下面按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:
这里做了简化，实际上，并不能如此干净利索地将大O运行时间转换为操作数，但就目前而 言，这种准确度足够了。
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。
总结：
- 二分查找的速度比简单查找快得多。
- O(log n)比O(n)快。需要搜索的元素越多，前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其
增速的角度度量的。 - 算法运行时间用大O表示法表示。
