date: 2017-9-16 11:11:15

title: 算法图解读书笔记

算法图解: http://www.ituring.com.cn/book/1864

套用面试时听到的一句话: 连 topk 问题都不知道, 我们不要计算机基础这么差的. 所以, 光看这本书, 还远远不够.

coding: https://coding.net/u/daydaygo/p/algorithm/git

一些概念

big O 表示法

对数(log)的理解: 可汗学院(khanacademy.org)有一个不错的视频

理解不同的大O运行时间

算法所需的固定时间量,被称为常量

平均情况和最糟情况

一些常见的大O运行时间

O(n!): 旅行商问题 阶乘函数(factorial function)

递归

基线条件 + 递归条件

编写涉及数组的递归函数时,基线条件通常是数组为空或只包含一个元素

循环 vs 递归: 程序的性能 vs 更容易理解

调用栈(call stack): 调用另一个函数时,当前函数暂停并处于未完成状态

尾递归: 对递归进行优化, 但并不是适用所有场景


NP完全问题: 没有快速算法的问题

数据结构

数组 vs 链表: facebook 查找用户名, 首字母作为数组, 数组的值为链表

队列(queue): 先进先出(First In First Out,FIFO)

栈(stack): 后进先出(Last In First Out,LIFO)

散列表(Hash Table)

场景: DNS解析(DNS resolution) / 缓存

散列函数: 防止重复 / SHA函数

冲突: 就在这个位置存储一个链表

填装因子

调整长度(resizing): 通常将数组增长一倍

一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

几乎根本不用自己去实现散列表

节点(node) + 边(edge)

有向图(directed graph)/ 无向图(undirected graph)

图还可能有环

权重(weight): 加权图(weighted graph) / 非加权图(unweighted graph)

负权边

二叉树 binary tree

二叉查找树(binary search tree)

平衡状态的特殊二叉查找树,如红黑树。

对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树

算法

二分查找: 40亿个 vs 32次查找

选择排序: 依次找出最小的数

快速排序: 选取基准值(pivot), 将序列分成大于基准值和小于基准值的 2 部分, 递归下去

合并排序(merge sort): 将序列依次分为 2 部分, 直到最小的可排序序列, 然后依次合并排序后的部分

广度优先搜索(breadth-first search,BFS)

场景: 最短路径问题(shortest-path problem)

  • 编写国际跳棋AI,计算最少走多少步就可获胜;
  • 编写拼写检查器
  • 人际关系网络找到关系最近的医生

使用队列实现时, 要注意保存节点是否访问过

big O: O(V + E),其中V 为顶点(vertice)数,E 为边数。


狄克斯特拉算法(Dijkstra's algorithm): 有向无环图(directed acyclic graph,DAG)

贝尔曼-福德算法(Bellman-Ford algorithm): 负权边的图

贪婪算法

场景: 教室调度问题 / 背包问题 / 集合覆盖问题

在有些情况下,完美是优秀的敌人

每步都选择局部最优解

近似算法(approximation algorithm): 速度有多快 / 得到的近似解与最优解的接近程度

动态规划

场景:

  • 背包问题: 当前的最大价值。
  • 最长公共子串,但其实更常用的是最长公共子序列
  • DNA链的相似性
  • git diff
  • 编辑距离(levenshtein distance)指出了两个字符串的相似程度
  • word 软件中换行

但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用

没有放之四海皆准的计算动态规划解决方案的公式。

K最近邻(k-nearest neighbours,KNN)

特征抽取: 毕达哥拉斯公式(2 点间的距离) / 余弦相似度(cosine similarity)

分类就是编组

回归(regression)就是预测结果(如一个数字)

场景: 推荐系统 / 橙子还是柚子


欧几里得算法: 两个正整数a,b的最大公约数 gcd(a,b)

分而治之(divide and conquer,D&C)

费曼算法(Feynman algorithm)


OCR(optical character recognition): 第一步是查看大量的数字图像并提取特征,这被称为训练(training)

朴素贝叶斯分类器(Naive Bayes classifier): 垃圾邮件过滤器

反向索引(inverted index): 搜索引擎

傅里叶变换: 绝妙优雅且应用广泛的算法之一 / 给它一杯冰沙, 它能告诉你其中包含哪些成分

并行算法: 并行性管理开销 / 负载均衡

MapReduce: 分布式算法 / 映射(map)函数和归并(reduce)函数

概率型算法: 布隆过滤器是一种概率型数据结构 / HyperLogLog近似地计算集合中不同的元素数 / 它提供的答案有可能不对,但很可能是正确的 / 面临海量数据且只要求答案八九不离十时

安全散列算法(secure hash algorithm,SHA)函数: 比较文件 / 检查密码

Simhash: 局部敏感的散列算法

Diffie-Hellman密钥交换: 如何对消息进行加密,以便只有收件人才能看懂呢?

线性规划: 线性规划用于在给定约束条件下最大限度地改善指定的指标 / Simplex算法

函数式编程一瞥

haskell // haskell: sum sum[] = 0 sum(x:xs) = x + (sum xs)