这篇文章是《图解算法》一书的摘抄总结。
原书标题是《Grokking Algorithms》，grok是中文“意会”的意思，韦伯斯特的解释是“to understand profoundly and intuitively ”，英语的原意是强调深入直观地理解。有意思的是，今年的最后一天，2017年12月31日，还会出版另一本Grokking书，《Grokking Deep Learning》（图解深度学习），哈哈，到时候也看看。
第1章 算法简介
二分查找
一般而言，对于包含n 个元素的列表，用二分查找最多需要log2(n) 步，而简单查找最多需要n 步。
二分查找算法如下：
def binary_search(list, item):
low = 0 （以下2行）low和high用于跟踪要在其中查找的列表部分
high = len(list)—1
while low <= high: ←-------------只要范围没有缩小到只包含一个元素，
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, 3) # => 1 ←--------------------别忘了索引从0开始，第二个位置的索引为1
print binary_search(my_list, -1) # => None ←--------------------在Python中，None表示空，它意味着没有找到指定的元素
习题
1.1 假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到？
1.2 上面列表的长度翻倍后，最多需要几步？
最多需要猜测的次数与列表长度相同，这被称为线性时间 （linear time）。二分查找的运行时间为对数时间 （或log时间）。
大O表示法
大O表示法指出了最糟情况下的运行时间。线性算法的运行时间为O (n )，对数算法的运行时间为O (log n )。
常见的大O运行时间（由快到慢）：
- O (log n )，也叫对数时间 ，这样的算法包括二分查找。
- O (n )，也叫线性时间 ，这样的算法包括简单查找。
- O (n * log n )，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
- O (n 2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
- O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。
一些总结：
- 算法的速度指的并非时间，而是操作数的增速。
- 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
- 算法的运行时间用大O表示法表示。
- O (log n )比O (n )快，当需要搜索的元素越多时，前者比后者快得越多。
练习
使用大O表示法给出下述各种情形的运行时间。
1.3 在电话簿中根据名字查找电话号码。
1.4 在电话簿中根据电话号码找人。（提示：你必须查找整个电话簿。）
1.5 阅读电话簿中每个人的电话号码。
1.6 阅读电话簿中姓名以A打头的人的电话号码。这个问题比较棘手，它涉及第4章的概念。答案可能让你感到惊讶！
第1章总结：
- 二分查找的速度比简单查找快得多。
- O (log n )比O (n )快。需要搜索的元素越多，前者比后者就快得越多。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
- 算法运行时间用大O表示法表示。
第2章 选择排序
数组和链表
数组的元素存储在内存中相连的位置。
链表中的元素可存储在内存的任何地方。
链表的优势在插入元素方面，但进行跳跃读取元素效率低，数组的优势在于读取效率高。
练习
2.1 假设你要编写一个记账的应用程序。
你每天都将所有的支出记录下来，并在月底统计支出，算算当月花了多少钱。因此，你执行的插入操作很多，但读取操作很少。该使用数组还是链表呢？
下面是常见数组和链表操作的运行时间。
有两种访问方式：随机访问 和顺序访问 。顺序访问意味着从第一个元素开始逐个地读取元素。链表只能顺序访问：要读取链表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更快，这是因为它们支持随机访问。很多情况都要求能够随机访问，因此数组用得很多。
练习
2.2 假设你要为饭店创建一个接受顾客点菜单的应用程序。这个应用程序存储一系列点菜单。服务员添加点菜单，而厨师取出点菜单并制作菜肴。这是一个点菜单队列：服务员在队尾添加点菜单，厨师取出队列开头的点菜单并制作菜肴。
你使用数组还是链表来实现这个队列呢？（提示：链表擅长插入和删除，而数组擅长随机访问。在这个应用程序中，你要执行的是哪些操作呢？）
2.3 我们来做一个思考实验。假设Facebook记录一系列用户名，每当有用户试图登录Facebook时，都查找其用户名，如果找到就允许用户登录。由于经常有用户登录Facebook，因此需要执行大量的用户名查找操作。假设Facebook使用二分查找算法，而这种算法要求能够随机访问——立即获取中间的用户名。考虑到这一点，应使用数组还是链表来存储用户名呢？
2.4 经常有用户在Facebook注册。假设你已决定使用数组来存储用户名，在插入方面数组有何缺点呢？具体地说，在数组中添加新用户将出现什么情况？
2.5 实际上，Facebook存储用户信息时使用的既不是数组也不是链表。假设Facebook使用的是一种混合数据：链表数组。这个数组包含26个元素，每个元素都指向一个链表。例如，该数组的第一个元素指向的链表包含所有以A打头的用户名，第二个元素指向的链表包含所有以B打头的用户名，以此类推。
假设Adit B在Facebook注册，而你需要将其加入前述数据结构中。因此，你访问数组的第一个元素，再访问该元素指向的链表，并将Adit B添加到这个链表末尾。现在假设你要查找Zakhir H。因此你访问第26个元素，再在它指向的链表（该链表包含所有以z打头的用户名）中查找Zakhir H。
请问，相比于数组和链表，这种混合数据结构的查找和插入速度更慢还是更快？你不必给出大O运行时间，只需指出这种新数据结构的查找和插入速度更快还是更慢。
选择排序
将数组元素按从小到大的顺序排列。先编写一个用于找出数组中最小元素的函数。
def findSmallest(arr):
smallest = arr[0] ←------存储最小的值
smallest_index = 0 ←------存储最小元素的索引
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
使用这个函数来编写选择排序算法。
def selectionSort(arr): ←------对数组进行排序
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr) ←------找出数组中最小的元素，并将其加入到新数组中
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
第2章总结：
- 计算机内存犹如一大堆抽屉。
- 需要存储多个元素时，可使用数组或链表。
- 数组的元素都在一起。
- 链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
- 在同一个数组中，所有元素的类型都必须相同（都为int、double等）。
第3章 递归
编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件 （base case）和递归条件 （recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
def countdown(i):
print i
if i <= 0: ←------基线条件
return
else: ←------递归条件
countdown(i-1)
调用栈：调用另一个函数时，当前函数暂停并处于未完成状态。这个栈用于存储多个函数的变量，被称为调用栈 。
练习
3.1 根据下面的调用栈，你可获得哪些信息？
使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。
练习
3.2 假设你编写了一个递归函数，但不小心导致它没完没了地运行。正如你看到的，对于每次函数调用，计算机都将为其在栈中分配内存。递归函数没完没了地运行时，将给栈带来什么影响？
第3章总结：
- 递归指的是调用自己的函数。
- 每个递归函数都有两个条件：基线条件和递归条件。
- 栈有两种操作：压入和弹出。
- 所有函数调用都进入调用栈。
- 调用栈可能很长，这将占用大量的内存。
第4章 快速排序
分而治之D&C的工作原理：
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。
练习
4.1 请编写前述sum 函数的代码。
4.2 编写一个递归函数来计算列表包含的元素数。
4.3 找出列表中最大的数字。
4.4 还记得第1章介绍的二分查找吗？它也是一种分而治之算法。你能找出二分查找算法的基线条件和递归条件吗？
快速排序
def quicksort(array):
if len(array) < 2:
return array ←------基线条件：为空或只包含一个元素的数组是“有序”的
else:
pivot = array[0] ←------递归条件
less = [i for i in array[1:] if i <= pivot] ←------由所有小于基准值的元素组成的子数组
greater = [i for i in array[1:] if i > pivot] ←------由所有大于基准值的元素组成的子数组
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([10, 5, 2, 3])
练习
使用大O表示法时，下面各种操作都需要多长时间？
4.5 打印数组中每个元素的值。
4.6 将数组中每个元素的值都乘以2。
4.7 只将数组中第一个元素的值乘以2。
4.8 根据数组包含的元素创建一个乘法表，即如果数组为[2, 3, 7, 8, 10]，首先将每个元素 都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。
第4章总结：
- D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
- 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O (n log n )。
- 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
- 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O (log n )的速度比O (n )快得多。
第5章 散列表
散列表适合用于：
- 仿真映射关系；
- 防止重复；
- 缓存/记住数据，以免服务器再通过处理来生成它们。
第5章总结：
- 你可以结合散列函数和数组来创建散列表。
- 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
- 散列表的查找、插入和删除速度都非常快。
- 散列表适合用于仿真映射关系。
- 一旦填装因子超过0.7，就该调整散列表的长度。
- 散列表可用于缓存数据（例如，在Web服务器上）。
- 散列表非常适合用于防止重复。
第6章 广度优先搜索
广度优先搜索的最终代码如下。
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = [] ←------------------------------这个数组用于记录检查过的人
while search_queue:
person = search_queue.popleft()
if person not in searched: ←----------仅当这个人没检查过时才检查
if person_is_seller(person):
print person + " is a mango seller!"
return True
else:
search_queue += graph[person]
searched.append(person) ←------将这个人标记为检查过
return False
search("you")
第6章总结：
广度优先搜索指出是否有从A到B的路径。
如果有，广度优先搜索将找出最短路径。
面临类似于寻找最短路径的问题时，可尝试使用图来创建模型，再使用广度优先搜索来解决问题。
有向图中的边为箭头，箭头的方向指定了关系的方向。
无向图中的边不带箭头，其中的关系是双向的。
队列是先进先出（FIFO）的。
栈是后进先出（LIFO）的。
第7章 狄克斯特拉算法
要计算非加权图中的最短路径，可使用广度优先搜索 。要计算加权图中的最短路径，可使用狄克斯特拉算法 。
node = find_lowest_cost_node(costs) ←------在未处理的节点中找出开销最小的节点
while node is not None: ←------这个while循环在所有节点都被处理过后结束
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): ←------遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n] > new_cost: ←------如果经当前节点前往该邻居更近，
costs[n] = new_cost ←------就更新该邻居的开销
parents[n] = node ←------同时将该邻居的父节点设置为当前节点
processed.append(node) ←------将当前节点标记为处理过
node = find_lowest_cost_node(costs) ←------找出接下来要处理的节点，并循环
第7章总结：
广度优先搜索用于在非加权图中查找最短路径。
狄克斯特拉算法用于在加权图中查找最短路径。
仅当权重为正时狄克斯特拉算法才管用。
如果图中包含负权边，请使用贝尔曼-福德算法。
第8章 贪婪算法
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题时，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。
