大O时间

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法。这个运行时间为O(n)。大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速。

  1. 算法的速度指的并非时间，而是操作数的增速。
  2. 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
  3. 算法的运行时间用大O表示法表示。
  4. O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

递归

编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分:基线 条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。

递归主要使用栈，使用栈虽然很方便，但是也要付出代价:存储详尽的信息可能占用大量的内存。每个函数调 用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况 下，你有两种选择。

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

快排

归纳证明分为两步：基线条件和归纳条件。

快排的独特之处在于，其排序的速度取决于基准值的选择。（高度依赖）

对于快排和合并排序来说，常量的影响非常大，快排的常量比合排小，因此，如果它们的运行时间都为O(nlogn),快排的速度将会更快。

散列表

缓存的原理就是使用散列表。

缓存是一种常用的加速方式，所有的大型网站都使用缓存，而缓存的数据则存储在散列表中。

散列表适用于：模拟映射关系，防止重复，缓存/记住数据，以免服务器再通过处理来生成它们。

散列表避免冲突：较低的填装因子，良好的散列函数。

填装因子为=占用数/位置总数。如果填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度。tips：一旦填装因子大于0.7就开始调整散列表的长度。

广度优先搜索

广度优先搜索使你能够找出两样东西的最短距离。

图由节点和边组成，图用于模拟不同的东西是如何连接的。

栈是后进先出，队列是先进先出

广度优先搜索的运行时间为O(V+E),V为顶点数，E为边数。

如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。

狄克斯特拉算法（Dijkstra’s algorithm）

（多看几次）

找出最快的路径

四个步骤

  1. 找出”最便宜”的节点,即可在最短时间内到达的节点，并确保没有到该节点的更便宜的路径。
  2. 更新该节点的邻居的开销，对该节点的邻居，检查是否有前往他们的更短路径，如果有，就更新其开销。
  3. 重复这个过程，直到对图中的每个节点都这样做了
  4. 计算最终路径

最后得到完整的交换路径使用 沿父节点回溯的方法。

最短路径值得并不一定是物理距离，也可能是让某种度量指标最小。

如果有负权边，就不能使用狄克斯特拉算法。这是因为算法选择了权重最低的边之后就不会对该点的最短路径进行更新。

在包含负权边的图中，要找出最短路径，可以使用贝尔曼-福德算法（BellMan-Ford algorithm）。

  1. 加权图》提高或降低某些边的权重。带有权重的图为加权图，否则为非加权图
  2. 计算非加权图的最短路径，可使用狄克斯特拉算法。图还可能有环
  3. 在无向图中，每条边都是一个环，狄克斯特拉算法只适用于有向无环图。

实现

Dijkstra’s algorithm 三个散列表分别用来记录图结构、节点的成本、节点的父节点

贪心算法

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

有些情况下，完美是优秀的敌人。

集合也不能包含重复的元素。

NP完全问题

需要计算所有的解，并从中选出最小/最短的那个。

面对NP完全问题，最佳的做法就是使用近似算法

动态规划

动态规划用于解决棘手问题，可将问题分为小问题，并先着手解决这些小问题。

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

背包问题

最长公共子串

K最近邻算法

  1. 特征抽取

使用KNN做两项基本工作：分类和回归。分类就是编组，回归就是预测结果。

OCR：光学字符识别。也是基于KNN简单理念。OCR的第一步是查看大量的数字图像并提取特征，这被称为训练。

算法介绍

  1. 二叉查找树
  2. 反向索引：一个散列表，将单词映射到包含它的页面。这种数据结构被称为反向索引。常用于创建搜索引擎。
  3. 傅里叶变换：傅里叶变换可将一首歌曲中的各种频率分离出来。还被用来地震预测和DNA分析。
  4. 并行算法：能在多个内核中并行执行的算法。
  5. 分布式算法：特殊的并行算法。如MapReduce.基于两个简单的理念：映射（map）函数和归并（reduce）函数。
  6. 布隆过滤器和HyperLogLog。布隆过滤器是一种概率性数据结构，它提供的答案有可能不对，但很有可能是正确的。HyperLogLog是一种类似于布隆过滤器的算法。
  7. SHA算法：SHA算法被广泛用于计算密码的散列值，这种散列算法是单向的。局部不敏感
  8. Simhash：局部敏感的散列算法，当需要检查两项内容的相似程度时，Simhash很有用。
  9. Diffie-Hellman：双方无需知道加密算法。
  10. 线性规划：用于在给定约束条件下最大限度地改善指定的指标。线性算法使用SImplex算法。

读后感

  1. 时间拖得太长，最早看的有一些内容已经忘记了。看完之后需要进行研究。