共计 1465 个字符，预计需要花费 4 分钟才能阅读完成。
在读《算法图解》这本书，这本书有两个优点：
手绘风格的图，看着很让人“入戏”；
算法采用 Python 语言描述，能更好的表达算法思想。
关于算法的学习有两点心得：
算法思想最重要，理解了思想，算法是很容易写出来的，所以尽量不要把过多精力放在细节上。比如，本书的快速排序，使用了列表推导式，很简单就把算法的思想描述了出来。相比而言，某些使用 C 语言的书籍给出的版本则比较难懂，归其原因是因为太突出细节了。细节不是不重要，而是我们要首先把算法能更好地理解，下一步才是实现和优化。
某些情况下递归比迭代更容易表达算法 递归是描述性的，侧重了对算法性质的表达；而迭代更侧重算法实现，往往掺杂了太多的实现细节。所以，我同时用 Haskell 给出递归版本的算法描述。
好了，开始。
引言
算法是一组完成任务的指令。任何代码片段都可视为算法。[注意：该书对算法的定义与通行的定义不同，通行的定义要求算法应该具有有穷性，即算法必须能在执行有限个步骤之后终止，否则算法是没有意义的。]
在本书中, 你将学习比较不同算法的优缺点: 该使用合并排序算法还是快速排序算法, 或者该使用数组还是链表。仅仅改用不同的数据结构就可能让结果大不相同。
二分查找（binary search）
其输入是一个有序的元素列表; 查找的元素包含在列表中, 二分查找返回其位置; 否则返回 Nothing。一般而言, 对于包含 n 个元素的列表, 用二分查找最多需要 log2n 步。
Python 版本：
def binary_search(list, item):
low = 0
high = len(list)—1
while low <= high:
mid = (low + high)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid – 1
else:
low = mid + 1
return None
Haskell 版本：使用了 Vector，因为标准库的列表是单链表，不支持随机访问。
import qualified Data.Vector as V
binarySearch :: (Ord a)=> V.Vector a -> Int -> Int -> a -> Maybe Int
binarySearch vec low high e
| low > high = Nothing
| vec V.! mid > e = binarySearch vec (mid+1) high e
| vec V.! mid < e = binarySearch vec low (mid-1) e
| otherwise = Just mid
where
mid = low + ((high-low) `div` 2)
大 O 表示法
仅知道算法需要多长时间才能运行完毕还不够, 还需知道运行时间如何随列表增长而增加。
算法的运行时间以不同的速度增加
算法的速度指的并非时间, 而是操作数的增速。谈论算法的速度时, 我们说的是随着输入的增加, 其运行时间将以什么样的速度增加。大 O 表示法让你能够比较操作数, 它指出了算法运行时间的增速。
大 O 表示法指出了最糟情况下的运行时间
这是一个保证——如，简单查找的运行时间不可能超过 O(n)。
一些常见的大 O 运行时间
O(log n), 也叫对数时间, 这样的算法包括二分查找。 O(n), 也叫线性时间, 这样的算法包括简单查找。 O(n * log n), 这样的算法包括快速排序——一种速度较快的排序算法。 O(n2), 这样的算法包括选择排序——一种速度较慢的排序算法。 O(n!), 这样的算法包括旅行商问题的解决方案——一种非常慢的算法
旅行商问题
旅行商要前往 n 个城市, 同时要确保旅程最短，时间复杂度：O(n!)。
请关注我的公众号哦。
