【笔记】迈向人工智能 | 《算法图解》：像小说一样有趣的算法入门书
推荐指数：★★★★☆
简短书评：这本书非常适合有基本编程基础（学过C或Python或任一门编程语言即可），而想入门算法的同学，图文并茂，简明易懂。书不厚，两百页左右，加上大量手绘示例图，很快就翻完了，却生动形象地介绍了基本的数据结构和算法，建议在看更专业的算法书之前，先过一下这本书。由于定位为入门，很多地方都只是简单提了一下，并未深入探讨，留待各位同学感兴趣的话自学。书中案例以Python或伪代码的形式呈现，就算不会编程语言，阅读起来也没什么难度。学习编程或算法一定要杜绝眼高手低，建议亲自敲敲书中的代码，完成课后不多的作业，相信会有收获。
第 1 章 算法简介
“二分查找”：相比简单顺序查找，在有序的列表中应用该算法将会提升查找效率，特别是随着列表增大的时候。
大O表示法：描述算法运行时间的增速（而非时间），指出了最糟情况下的运行时间，如O(log n)和O(n)。
第 2 章 选择排序
数组：元素地址在内存中相邻。读取速度快，支持随机访问， O(1) 。插入（预留位置容易造成内存浪费和需要转移）以及删除元素不方便，O(n)。
链表：每个元素存储下一个元素地址。同时读取所有元素时，效率高，但如果需要跳跃，效率很低，O(n)。插入和删除元素速度快，O(1)。
选择排序：每次从剩下的元素中找出最大/小的元素，完成排序，时间复杂度为O(n2)。
第 3 章 递归
递归：在函数中调用函数本身。包含基线条件 （base case）和递归条件 （recursive case）。
递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。
调用栈：所有函数调用都进入调用栈，通过入栈和出栈完。调用栈可能很长（特别是在递归中），这将占用大量的内存，可以转而使用循环或尾递归。
第 4 章 快速排序
分而治之（Divide and Conquer, D&C）：一种著名的递归式问题解决方法，① 找出简单的基线条件； ② 确定如何缩小问题的规模，使其符合基线条件。
快速排序：① 随机选择基准值；② 将数组分成两个子数组：小于基准值的元素和大于基准值的元素；③ 对这两个子数组进行快速排序；依此递归。
大O表示法：固定时间量c，通常不考虑，在相同时间复杂度情况下可能会有所影响。快速排序平均运行时间：O(nlog n)，最糟情况为：O(n2)。
第 5 章 散列表
散列函数：总是将同样的输入映射到相同的索引，将不同的输入映射到不同的索引。
散列表：一种数据结构（Key-Value），结合散列函数和数组，使用散列函数来确定元素的存储位置。查找、插入和删除速度都非常快，适用于模拟映射关系，防止重复，缓存。
冲突 ：给两个键分配的位置相同。简单解决方法是：如果两个键映射到了同一个位置，就在这个位置存储一个链表。但如果散列表存储的链表很长，散列表的速度将急剧下降。要避免冲突，散列函数需要有：较低的填装因子（散列表包含元素数/位置总数，一旦填装因子超过0.7，就该调整散列表的长度）； 良好的散列函数（均匀映射）。
第 6 章 广度优先搜索
图：由节点 （node）和边 （edge）组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。图分有效图/无效图。
队列：先进先出（FIFO）；栈：先进后出（LIFO）；
广度优先搜索回答两类问题。 第一类问题：从节点A出发，有前往节点B的路径吗？ 第二类问题：从节点A出发，前往节点B的哪条路径最短？
实现算法：① 创建一个队列，用于存储待检查的对象；② 从队列中弹出一个对象；③ 检查这个对象是否满足对象；④ 如果不是将这个对象的所有邻居加入队列；⑤ 回到第2步继续执行，直至队列为空或找到目标；（注意：检查完一个对象后，应将其标记为已检查，且不再检查它。）
运行时间：O (V + E )，其中V 为顶点（vertice）数，E 为边数。
第 7 章 狄克斯特拉算法
树：一种特殊的图，其中没有往后指的边。
狄克斯特拉算法：用于在加权图中查找最短路径，仅当权重为正时才管用，如果包含负权边，可使用贝尔曼·福德算法。
实现算法：① 找出“最便宜”的节点，即可在最短时间内到达的节点；② 更新该节点的邻居的开销；③ 重复这个过程，直到对图中的每个节点都这样做；④ 计算最终路径。
狄克斯特拉算法背后的关键理念：找出图中最便宜的节点，并确保没有到该节点的更便宜的路径 ！这种假设仅在没有负权边时才成立。
第 8 章 贪婪算法
集合：类似于列表，只是不能包含重复的元素，可执行并集、交集和差集操作。
贪婪算法：寻找局部最优解，企图以这种方式获得全局最优解。
NP完全问题：① 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢；② 涉及“所有组合”的问题通常是NP完全问题；③ 不能将问题分成小问题，必须考虑各种可能的情况，这可能是NP完全问题；④ 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题；⑤ 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题；⑥ 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
对于NP完全问题，还没有找到快速解决方案，最佳的做法是使用近似算法（速度有多快；近似解与最优解的接近程度）。
第 9 章 动态规划
动态规划：给定约束条件下找到最优解，在问题可分解为彼此独立且离散的子问题时，就可使用动态规划来解决。
每种动态规划解决方案都涉及网格，单元格的值就是要优化的值，每个单元格都是一个自问题，所以应该考虑如何将问题分成子问题，这有助于找出网格的坐标轴。
第 10 章 K最近邻算法
KNN：用于分类和回归，需要考虑最近的邻居。分类就是编组（橙子还是柚子）；回归就是预测结果（如一个数字）。
特征抽取：意味着将物品（如水果或用户）转换为一系列可比较的数字，能否挑选合适的特征事关KNN算法的成败（紧密相关，不偏不倚）。
距离计算：毕达哥拉斯公式，或余弦相似度。
第 11 章 接下来如何做
二叉查找数：对于其中的每个节点，左子节点的值都比它小，而右子节点的值都比它大。在二叉查找树中查找节点时，平均运行时间为O(log n)，但在最糟的情况下所需时间为O(n)；相比有序数组，二叉查找数插入和删除操作的速度要快得多，但也存在一些缺点，如不能随机访问。可了解B树，红黑树，堆，伸展树等内容。
反向索引 （inverted index）：如一个散列表，将单词映射到包含它的页面，常用于创建搜索发动机。
傅里叶变换：如果能够将歌曲分解为不同的频率，就可强化你关心的部分，如强化低音并隐藏高音。傅里叶变换非常适合用于处理信号，可使用它来压缩音乐。
并行算法：设计起来很难，要确保它们能够正确地工作并实现期望的速度提升也很难。有一点是确定的，那就是速度的提升并非线性的，必须考虑到并行性管理开销和负载均衡。
MapReduce：基于两个简单的理念——映射（map ）函数和归并（reduce ）函数。
布隆过滤器：一种概率型数据结构 ，它提供的答案有可能不对，但很可能是正确的。使用散列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。布隆过滤器的优点在于占用的存储空间很少。HyperLogLog：近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案，但也八九不离十，而占用的内存空间却少得多。
安全散列算法（secure hash algorithm，SHA）函数：给定一个字符串，SHA返回其散列值。SHA被广泛用于计算密码的散列值，这种散列算法是单向的。
局部敏感的散列算法：有时候，你希望结果相反，即希望散列函数是局部敏感的，需要检查两项内容的相似程度时，Simhash很有用。
Diffie-Hellman算法及其替代者RSA依然被广泛使用。它使用两个密钥：公钥和私钥，来进行加解密。
线性规划：用于在给定约束条件下最大限度地改善指定的指标。
附：部分算法Python代码
# Binary Search def binary_search(list, item): low = 0 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
# Selection Sort def selectionSort(arr): newArr = [] for i in range(len(arr)): smallest = findSmallest(arr) newArr.append(arr.pop(smallest)) return newArr def findSmallest(arr): smallest = arr[0] smallest_index = 0; for i in range(1, len(arr)): if arr[i] < smallest: smallest_index = i smallest = arr[i] return smallest_index
# Recursion def fact(x): if x == 1: #基线条件 return 1 else: #递归条件 return x * fact(x-1)
# Quick Srot 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)
#Breadth-First Search from collections import deque 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
# Dijkstras Algorithm node = find_lowest_cost_node(costs)
while node is not None: 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）
# Greedy Algorithm while states_needed: best_station = None states_covered = set() for station, states in stations.items(): covered = states_needed & states if len(covered) > len(states_covered): best_station = station states_covered = covered states_needed -= states_covered final_stations.add(best_station
