算法图解读书笔记

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: sum
sum[] = 0
sum(x:xs) = x + (sum xs)