一本非常基础的算法书，补补脑子。

一、大O表示法

  • 算法的运行时间以不同的速度增加
  • 大O表示法指出了最糟情况下的运行时间
  • 一些常见的大O运行时间
    • O(log n) 对数时间，比如二分查找
    • O(n) 线性时间，比如简单查找
    • O(n * logn) 快速排序
    • O(n^2) 选择排序
    • O(n!) 非常慢
  • 大O中省略常数

Summary 1.

  • 二分查找的速度比简单查找快得多
  • O(log n) 比 O(n) 快
  • 算法运行时间并不以秒为单位
  • 算法运行时间是从其增速的角度度量的
  • 算法运行时间用大O表示法表示

二、选择排序

  • 内存：每个抽屉都有地址，存入的东西都记录地址
  • 数组和链表
    • 数组：读取快
    • 链表：插入、删除快
  • 选择排序 O(n^2) 每次拿出剩余的最大/小项，共进行 n * n 次

Summary 2.

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

三、递归

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

四、快速排序

  • D&C算法是递归的。

    1. 找出基线条件，这种条件必须尽可能简单。
    2. 不断将问题分解（或者说缩小规模），直到符合基线条件。

  • 复杂度 O(n * logn) （同归并排序）

  • 欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。

    1
    2
    3
    4
    function gcd(a, b) {
      if (a % b == 0) return b;
      return gcd(b, a % b);
    }

  • 函数式编程是声明式的一种类型，声明式强调目标而不是具体过程。

Summary 4.

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

五、散列表 Hash tabe

  • 散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个数字。因此，你可首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来确定鳄梨的价格存储在什么地方。
  • 散列函数将不同的输入映射到不同的索引。avocado映射到索引4，milk映射到索引0。每种商品都映射到数组的不同位置，让你能够将其价格存储到这里。
  • 散列函数知道数组有多大，只返回有效的索引。如果数组包含5个元素，散列函数就不会返回无效索引100。
  • O(1) - O(n)
  • 在平均情况下，散列表的查找(获取给定索引处的值)速度与数组一样快
  • 填装因子大于1意味着商品数量超过了数组的位 置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度(resizing)。填装因子越低，发生冲突的可能性越小，
    散列表的性能越高。
  • 一旦填装因子超过0.7，就该调整散列表的长度。

Summary 5.

散列表适用于：

  • 模拟映射关系;
  • 防止重复;
  • 缓存/记住数据，以免服务器再通过处理来生成它们。

而要避免冲突，需要有:

  • 较低的填装因子;
  • 良好的散列函数。
  • 图用于模拟一组连接。图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。
  • 广度优先搜索：
  1. 广度优先搜索指出是否有从A到B的路径。
  2. 如果有，广度优先搜索将找出最短路径。
  3. 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来
    解决问题。
  4. 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。
  5. 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约
    会，而rachel也与ross约会”。
  6. 队列是先进先出(FIFO)的。
  7. 栈是后进先出(LIFO)的。
  8. 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必
    须是队列。
  9. 对于检查过的人，务必不要再去检查，否则可能导致无限循环。

七、狄克斯特拉算法

  • 广度优先搜索找出的是段数最少的路径。如果要找出最快的路径可使用另一种算法——狄克斯特拉算法(Dijkstra’s algorithm)。
  1. 找出最便宜的（权重最小）节点
  2. 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
  3. 重复这个过程，直到对图中的每个节点都这样做了。
  4. 计算最终路径。
  • 加权图(weighted graph)
  • 非加权图(unweighted graphQ34567809 -=
    在无向图中，每条边都是一个环。狄克斯特拉算法只适用于有向无环图(directed acyclic graph，DAG)。

实现

要编写解决这个问题的代码，需要三个散列表。

Summary 7.

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

八、贪婪算法

  • 每步都选择局部最优解，最终得到的就是全局最优解。

教室分配课程：
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。
(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要
在这间教室上的第二堂课。

NP完全问题

  • 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
  • 涉及“所有组合”的问题通常是NP完全问题。
  • 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
  • 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
  • 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
  • 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

Summary 8.

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

九、动态规划

  • 动态规划从小问题着手，逐步解决大问题

Summary 9.

需要在给定约束条件下优化某种指标时，动态规划很有用。

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

十、K最近邻算法

  • K：和目标最近的K个近邻

特征抽取

  1. 抽取它们的特征，再根据特征绘图
  2. 计算两坐标距离

OCR指的是光学字符识别，使用KNN算法

  • OCR的第一步是查看大量的数字图像并提取特征，这被称为训练（training）。大多数机器学
    习算法都包含训练的步骤：要让计算机完成任务，必须先训练它。下一个示例是垃圾邮件过滤器，
    其中也包含训练的步骤。

Summary 10.

KNN用于分类和回归，需要考虑最近的邻居。

  • 分类就是编组。
  • 回归就是预测结果（如数字）。
  • 特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。
  • 能否挑选合适的特征事关KNN算法的成败。