这是对《算法图解》这本书的阅读总结，记录了《算法图解》一文的收获与感悟。。

第 01 章——算法简介

二分查找（有序序列）

大O表示法：表示最坏条件下，操作数的增速

常见大O运行时间（快到慢）

时间说明
O（logn）对数时间，二分查找
O（n）线性时间，简单查找
O（n*logn）快速排序
O（n^2）选择排序
O（n！）旅行商问题

实例

旅行商问题：前往n个地点，总旅程的最短路线。

第 02 章——选择排序

  • 数组：内存连续，查询快，增删元素慢
  • 链表：内存不连续，查询慢，增删元素快
  • 链表数组：查询，增删元素介于数组和链表
  • 选择排序：(1/2)n^2 #大O表示法忽略常数

实例

Facebook创建用户时，用链表数组：26个数组元素里面存放链表

第 03 章——递归

  • 递归：调用自己
  • 基准条件（base）
  • 递归条件（recursive）
  • 调用栈（call stack）：先进后出，只有压入和弹出操作，内存占用可能很大

调用另外一个函数时，当前函数暂停，处于未完成状态

递归也调用了栈，当不为基准条件时，压入，为基准条件时，弹出

第 04 章——快速排序

  • 分而治之（divide and conquer，D&C）
  1. 找出基准条件，尽量简单
    2.不断分解问题（或缩小规模），直到符合基准条件

欧几里得算法

函数式编程

快速排序

  1. 选择一个元素，作为基准值（pivot）
  2. 按<、>基准值，进行分区（partitioning）
  3. 对<、>基准值得子数组，进行快速排序，最后合并。
  • 最糟糕情况：O(n^2)
  • 平均情况（最佳情况）：O(n log n)
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[i: ] if i > pivot ]
        return quicksort( less ) + [pivot] +quicksort( greater )

归纳证明

合并排序（merge sort）

最糟糕情况：O(n log n)
最佳情况（平均情况）

大O时间表示法：O(n) = C * n

常量C：算法所需的固定时间

第 05 章——散列表

散列函数：将输入映射为数字（作为数组的索引）

  1. 将同样的输入映射到相同的索引
  2. 尽量将不同的输入映射到不同的索引
  3. 如果映射到同一个索引上，就在这个位置创建一个存储链表
  4. 不超过数组长度，只返回有效的索引

散列表（hashmap）：也叫，字典，映射，关联数组，通过散列函数，把value值存放到对应数组索引

  • 平均情况下：O( 1)

  • 最糟糕情况下：O( n )

  • 较低的装填因子：包含的元素/总位置数（通常为3/4），大于就调整长度为原来的1倍

  • 良好的散列函数：SHA函数

作用

  • 用于查找、删除、插入：DNS解析、DNS resolution（网站映射到ip地址）
  • 防止重复：投票
  • 用于缓存：保存用户数据，下次直接返回数据

第 06 章——广度优先搜索

  • 图：由节点（node）和边（edge）组成。
  • 邻居：相连的俩个节点、
  • 有向图（directed graph）：有方向
  • 无向图（undirected graph）：无方向

广度优先搜索（breadth-first search，BFS）

用图来建立问题模型
使用广度优先搜索（先一度关系，再二度关系）
使用队列添加顺序检查（检查过的人不必再检查
运行时间：O( V + E ) , V是顶点数（vertice），E为边数

  • 队列（queue）：先进先出（First in First out，FIFO）
  • 拓扑排序：A依赖与B，A必须在B任务后面。

作用：解决最短路径问题：shortest-path problem

  1. 从A出发，是否有路径到B
  2. 从A出发，到B那条路径最短

第 07 章——狄克斯特拉算法

  • 加权图（weighted graph）：每条边都有固定关联数字（权重），有权重的图。
  • 非加权图（unweighted graph）：没有权重的图
  • 负权边：权重为负

狄克斯特拉算法（Dijkstra‘s algorithm）：找出最快的路径

  1. 找出最便宜的节点
  2. 更新该节点邻居的开销（权重）
  3. 重复这个步骤，直到所有节点都做了
  4. 计算最终路径

只适合有向无环图（directed acyclic graph，DAG）
有负权边则不可使用（可使用，贝尔曼-福德算法）

第 08 章——贪婪算法

  • 贪婪算法：每步都选择局部最优解。
  • 只能接近最优解，有时候并不是最优解

集合覆盖问题

  • 幂集（power set）：每个可能的子集。2^n个
  • 并集：集合合并
  • 交集：都有的元素集合
  • 差集：除去另外一个集合有的元素

近似算法（approximation algrithm）：解决NP完全问题

  • 速度有多快
  • 得到近似解与最优解的接近程度

NP完全问题：为了解决集合覆盖问题，必须计算每个可能的集合 O( n! )

  • 必须考虑各种情况
  • 阶乘函数（factorial function）

第 09 章——动态规划

  • 动态规划：将问题分成小问题，并先着手解决这些小问题。

  • 最长子公共字串

  • 最长公共子序列

第 10 章——K最近邻算法

K最近邻算法（K-nearest neighbours,KNN）：通过最接近的对象，判断本物体是什么？（或者喜欢什么）

  • 毕达哥拉斯公式：（计算俩点距离）a2+b2=c^2
  • 特征抽取：选出紧密相关，不偏不倚的特征，进行对比判断。（转换为数字）
  • 余弦相识度（cosine similarity）
  • 分类：是编组
  • 回归（regression）：预测结果

应用

  • 分类系统

  • 推荐系统

  • 机器学习：

    • OCR，光学字符识别（optical character recognition）：拍摄印刷页面的照片，识别出其中的文字。
    • 训练（training）：浏览大量的数字图像，提取数字特征（曲线，点，线段）
    • 遇到新图像时，提取该特征，找出最近的邻居是谁

  • 垃圾邮件过滤器：

朴素贝叶斯分类器（Naive Bayes classifier）：对特定数据进行训练，然后判断是垃圾邮件的概率。

第 11 章——接下来如何做

二叉查找树（binary search tree）：
每个节点：左子节点比它小，右子节点比它大。

  • 先检查根节点。

优点：

  • 效率，跟二分查找一致。
  • 删除和插入的效率要快。

缺点：

  • 不能随机访问

  • 红黑树：处于平衡状态的特殊二叉查找树

  • B树：一种特殊的二叉树，数据库用它于存储数据

  • 堆：

  • 伸展树：

搜索引擎的原理

  • 反向索引：创建一个散列表，将键为单词，值为包含指定单词的页面，一个散列表，将单词映射到包含它的页面。

  • 傅里叶变换：强化你关心的部分，用于处理信号。

  • 并行算法：多个内核中并行的处理。

并行性管理开销
负载均衡
分布式算法：一种特殊的并行算法，MapReduce。用于短时间内完成，海量工作。

  • 映射（map）函数：接受一个数组，对每个元素执行同样的处理。
  • 归并（reduce）函数：将很多项归并为一项。一个数组转换为一个元素。
  • 布隆过滤器：一种概率型数据结构，提供的答案可能对，也可能不对。很可能正确。占用存储空间很少。

HyperLogLog：一种类似布隆过滤器算法，答案比较接近准确，占用内存少。

SHA算法（安全散列算法）：给定一个字符串，返回其散列值。局部不敏感。

  • 可以用于判断俩个文件是否相同。
  • 检查密码，存储哈希值。
  • 局部不敏感。simhash。
  • Diffie-Hellman密钥交换。

公钥：用于加密消息
私钥：用于解密消息
RSA算法

线性规划：最优化，在给定约束条件下最大限度地改善指定的指标。

Simplex算法。