算法图解

精读完这部分，已经开始觉得吃力了。我觉得需要暂停阅读，消化一下再继续往后阅读。

I. 问题解决技巧：

• 二分查找的速度比简单查找快得多
• 0(log n)比0(n)快。需要搜索的元素越多，前者比后者快得越多
• 算法运行时间并不以秒为单位
• 算法运行时间是从其增速的角度度量的
• 算法运行时间用大0表示法表示

II. 选择排序链表：linked list数组：array

• 计算机内存犹如一大堆抽屉
• 需要存储多个元素时，可使用数组或链表
• 数组的元素都在一起
• 链表的元素是分开的，其中每个元素都存储 下一个元素的地址
• 数组的读取速度很快
• 链表的插入和删除速度很快
• 在同一个数组中，所有元素的类型都必须相同（都为int、double等）

III. 递归Recursion如果使用循环，程序的性能可能会更高。如果使用递归，程序可能更容易理解Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!每个递归函数都有两部分：

• 基线函数base case：函数调用自己
• 递归条件recursive case：函数不再调用自己，从而避免形成无限循环

调用栈call stack Resumé:

• 递归指的是调用自己的函数
• 每个递归函数都有两个条件：基线条件和递归条件
• 栈有两种操作：压入和弹出
• 所有函数调用都进入调用栈
• 调用栈可能很长，这将占用大量的内存

IV. 快速排序分而治之（divide and conquer, D&C)

1. 找出简单的基线条件
2. 确定如何缩小问题的规模，使其符合基线条件

分区partitioning Resumé:

• D&C 将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组
• 实现快速排序时，请随机选择用作基准值的元素。快速排序的平均运行时间为0(n log n)
• 大0表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因
• 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，0(log n)的速度比0(n)快

V. 散列表 hash table散列函数：将输入映射到数字散列表hash table

• 模拟映射关系
• 防止重复
• 缓存/记住数据

冲突collision：给两个键分配的位置相同>>如果两个键分配的位置相同，就在这个位置存储一个链表 Resumé:几乎不用自己去实现散列表，因为你的编程语言提供了散列表实现。你可使用Python提供的散列表，并假定能够获得平均情况下的性能：常量时间

• 你可以结合散列函数和数组来创建散列表
• 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数
• 散列表的查找、插入和删除都非常快
• 散列表适用于模拟映射关系
• 一旦填装因子超过0.7，就应该调整散列表的长度
• 散列表可用于缓存数据
• 散列表非常适用于防止重复

VI. 广度优先搜索 Breath-first search, BFS找出两样东西之间的最短距离最短路径问题shortest-path problem图由节点node和边edge组成广度优先搜索可以回答两类问题：

• 从节点A出发，有前往节点B的路径吗
• 从节点A出发，前往节点B的哪条路径最短

队列queue

• 队列：先进先出的数据结构First in First out, FIFO
• 栈：后进先出的数据结构Last in First out, LIFO

拓扑排序 topological sorting

Resumé:

• 广度优先搜索指出是否有从A到B的路径
• 如果有，广度优先搜索将找出最短路径
• 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题
• 有向图中的边为箭头，箭头的方向指定了关系的方向
• 无向图中的边不带箭头，其中的关系是双向的
• 队列是先进先出的FIFO
• 栈是后进先出的LIFO
• 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列
• 对于检查过的人，务必不要再检查，否则可能导致无限循环

VII. 狄克丝特拉算法Dijkstra's algorithm权重weight；带权重的图是加权图 weighted graph；不带权重的图称为非加权图unweighted graph狄克丝特拉算法只适用于有向无环图directed acyclic graph, DAG贝尔曼——福德算法Bellman-Ford algorithmResumé:

• 广度优先搜素用于在非加权图中查找最短路径
• 狄克拉斯特算法用于在加权图中查找最短路径
• 仅当权重为正时狄克拉斯特算法才管用
• 如果图中包含负权边，请使用贝尔曼——福德算法

VIII. 贪婪算法 Greedy algorithm每步都选择局部最优解近似算法approximation algorithm阶乘函数factorial functionResumé:

• 贪婪算法寻找局部最优解
• 对于NP完全问题，还没有找到快速解决方案
• 面临NP完全问题时，最佳的做法是使用近似算法
• 贪婪算法易于实现、运行速度快，是不错的近似算法

IX. 动态规划Dynamic programming (DP)费曼算法Feynman algorithm

1. 将问题写下来
2. 好好思考
3. 将答案写下来

Resumé:

• 需要在给定约束条件下优化某种指标时，动态规划很管用
• 问题可分解为离散子问题时，可使用动态规划来解决
• 每种动态规划解决方案都涉及网格
• 单元格中的值通常就是你要优化的值
• 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题
• 没有放之四海而皆准的计算动态规划解决方案的公式

X. K最近邻算法K-nearest neighbours, KNN余弦相似度cosine similarity光学字符识别OCR: optical character recognition朴素贝叶斯分类器Naive bayers classifierResumé:

• KNN用于分类和回归，需要考虑最近的邻居
• 分类就是编组
• 回归就是预测结果（如数字）
• 特征抽取意味着将物品转换为一系列可比较的数字
• 能否挑选合适的特征事关KNN算法的成败

XI. 接下来如何做

• 二叉查找树Binary search tree
• 反向索引inverted index
• 傅里叶变换
• 并行算法
  • 分布式算法, e.g. MapReduce，基于映射map函数和归并reduce函数
• 布隆过滤器和HyperLogLog
• SHA(secure hash algorithm)算法：安全散列算法
• Diffie-Hellman密钥交换
• 线性规划：在给定约束条件下最大限度地改善指定的指标，simplex算法

// the graph

const graph = {}

graph["start"] = {}

graph["start"]["a"] = 6 graph["start"]["b"] = 2

graph["a"] = {}

graph["a"]["fin"] = 1

graph["b"] = {}

graph["b"]["a"] = 3 graph["b"]["fin"] = 5

graph["fin"] = {}

// The costs table

const costs = {};

costs['a'] = 6 costs['b'] = 2;

costs['fin'] = Infinity;

// the parents table

const parents = {};

parents['a'] = 'start';

parents['b'] = 'start';

parents['fin'] = null;

let processed = [];

function find_lowest_cost_node(costs) {

let lowest_cost = Infinity;

let lowest_cost_node = null;

// Go through each node

for (let node in costs) {

let cost = costs[node];

// If it's the lowest cost so far and hasn't been processed yet...

if (cost < lowest_cost && (processed.indexOf(node) === -1)) {

// ... set it as the new lowest-cost node.

lowest_cost = cost;

lowest_cost_node = node;

}

}

return lowest_cost_node;

}

let node = find_lowest_cost_node(costs);

while (node !== null) {

let cost = costs[node];

// Go through all the neighbors of this node

let neighbors = graph[node];

Object.keys(neighbors).forEach(function(n) {

let new_cost = cost + neighbors[n];

// If it's cheaper to get to this neighbor by going through this node

if (costs[n] > new_cost) {

// ... update the cost for this node

costs[n] = new_cost;

// This node becomes the new parent for this neighbor.

parents[n] = node;

}

});

// Mark the node as processed

processed = processed.concat(node);

// Find the next node to process, and loop

node = find_lowest_cost_node(costs);

}

console.log("Cost from the start to each node:");

console.log(costs); // { a: 5, b: 2, fin: 6 }

NP完全问题的简单定义是， 以难解著称的问题， 如旅行商问题和集合

覆盖问题。 很多非常聪明的人都认为， 根本不可能编写出可快速解决这

些问题的算法

但如果要找出经由指定几个点的的最短路径， 就是旅行商问题——NP 完全问题。 简言之， 没办法判断问题是不是NP完全问题， 但还是有一 些蛛丝马迹可循的。 元素较少时算法的运行速度非常快， 但随着元素数量的增加， 速度 会变得非常慢。 涉及“所有组合”的问题通常是NP完全问题。 不能将问题分成小问题， 必须考虑各种可能的情况。 这可能是NP 完全问题。 如果问题涉及序列（ 如旅行商问题中的城市序列） 且难以解决， 它 可能就是NP完全问题。 如果问题涉及集合（ 如广播台集合） 且难以解决， 它可能就是NP 完全问题。 如果问题可转换为集合覆盖问题或旅行商问题， 那它肯定是NP完 全问题。

贪婪算法寻找局部最优解， 企图以这种方式获得全局最优解。

对于NP完全问题， 还没有找到快速解决方案。

面临NP完全问题时， 最佳的做法是使用近似算法。

贪婪算法易于实现、 运行速度快， 是不错的近似算法。