AlgorithmIntroduce

对于一个给定函数 \(g(n)\) ,用 \(\Theta(g(n))\) 来表示函数集合：
\(\Theta(g(n)) = \{f(n):存在常数 c_1,c_2 和 n_0，使对所有的 n \geq n_0 ,有 0 \leq c_1g(n) \leq f(n) \leq c_2g(n)\} \quad 也就是说，对于任一函数 f(n),若存在正常数 c_1,c_2,使当 n 充分大时，f(n)能被夹在 c_1g(n)和 c_2g(n)中间，则 f(n)属于集合 \Theta(g(n))\)
\(\Theta 记号 给出了函数 f(n)的上下界\)

对于一个给定函数 \(g(n)\) ,用 \(O(g(n))\) 来表示函数集合：
\(O(g(n)) = \{f(n):存在常数 c 和 n_0，使对所有的 n \geq n_0 ,有 0 \leq f(n) \leq cg(n)\} \quad 也就是说，对于任一函数 f(n),若存在正常数 c,使当 n 充分大时，f(n)的值都在 cg(n)之下，则 f(n)属于集合 O(g(n))\)
\(O 记号 给出了函数 f(n)的上界\)

对于一个给定函数 \(g(n)\) ,用 \(\Omega(g(n))\) 来表示函数集合：
\(\Omega(g(n)) = \{f(n):存在常数 c 和 n_0，使对所有的 n \geq n_0 ,有 0 \leq cg(n) \leq f(n) \} \quad 也就是说，对于任一函数 f(n),若存在正常数 c,使当 n 充分大时，f(n)的值都在 cg(n)之上，则 f(n)属于集合 \Omega(g(n))\)
\(\Omega 记号 给出了函数 f(n)的下界\)

对于一个给定函数 \(g(n)\) ,用 \(o(g(n))\) 来表示函数集合：
\(o(g(n)) = \{f(n):对任意正常数 c ,存在常数 n_0 > 0，使对所有的 n \geq n_0 ,有 0 \leq f(n) < cg(n)\}\)
\(o 记号 给出了函数 f(n)的非渐近紧确上界\)

对于一个给定函数 \(g(n)\) ,用 \(\omega(g(n))\) 来表示函数集合：
\(\omega(g(n)) = \{f(n):对任意正常数 c ,存在常数 n_0 > 0，使对所有的 n \geq n_0 ,有 0 \leq cg(n) < f(n) \}\)
\(\omega 记号 给出了函数 f(n)的非渐近紧确下界\)

\(X(g(n))是一个集合，可以用 f(n) \in X(g(n)) 来表示 f(n)属于 X(g(n))。不过通常写为 f(n) = X(g(n))来表示这种关系。需要注意的是不能写为 X(g(n)) = f(n)\)
一般来说，当渐近记号出现在某个公式中时，我们将其解释为一个不在乎其名称的匿名函数。

• 用代换法解递归式需要两个步骤：
  
  1. 猜测解的形式
     
  2. 用数学归纳法找出使解真正有效的常数。
     
• 使用数学归纳法进行证明的步骤
  
  • 数学归纳法第一种形式
    
    1. 证明当 m=1 时命题成立。
       
    2. 假设 m=n 时命题成立，推导出在 m=n+1 时命题也成立。（n 代表任意自然数）
       
  • 数学归纳法第二种形式
    
    1. 证明当 m=1 时命题成立
       
    2. 假设 m<n 时命题成立，推导出在 m=n 时命题也成立。（n 代表任意自然数）
       

如下图利用递归树方法求解 \(T(n) = 3T(n/4) + c n ^2\)

主方法是递归树的一种应用。可以通过递归树来证明主方法。主方法所依赖的主定理如下：

HIRE-ASSISTANT(n)
  best = 0 // candidate 0 is a least-qualified dummy candidate
  for i=1 to n
    do interview candidate i
    if candidate i is better than candidate best
      then best = i
           hire candidate i

计算雇佣一个新的办公助理的期望次数

二叉堆在数组中构建的二叉树结构。其主要操作以及对应的时间复杂度如下：

堆相关代码实现请参考如下文件
AlgorithmIntroduce/Code_Heap.lua

• 快速排序的思路
  选择数组中第一个元素 A 为主元素(标准元素)，将数组元素分两部分第一部分为小于等于 A 的元素，第二部分为大于 A 的元素，然后递归对这两部分继续使用快速排序。
  
• 快速排序采用了分治法
  
• 快速排序是一种原地排序，不需要额外空间
  

比较排序可以被抽象为决策树。一棵决策树是一棵满二叉树，表示某排序算法作用于给定输入所做的所有比较，而控制结构、数据移动等都被忽略。

计数排序的思路为：确定数组中数据范围 Range(a,b)，创建一个计数数组，该数组以范围 Range(a,b)内的所有数据为索引，初始化计数数组的值为 0，遍历数组中元素，将其对应于计数数组的元素加 1，最后遍历计数数组得到排序后的元素。
计数排序的时间复杂度为 \(\Theta(n)\)
计数排序具有稳定性。排序算法的稳定性是指具有相同值的元素在输出数组中的相对次序与它们在输入数组中的次序相同。

基数排序的思路为：从低位到高位，对数组中每个元素的各个数据位进行排序，对位的排序完成，就得到了排序后的数据。
如果基数排序用到的稳定排序的时间复杂度为 \(\Theta(n)\) ,基数排序中最大数的位数为 mdn(即 max_digit_number),则基数排序的时间复杂度为 \(\Theta(mdn*n)=\Theta(n)\)

桶排序的思路为：将[0,1]范围化分为 bucket_size 部分，此处 0 对应数组元素最小值，1对应数组元素最大值，bucket_size 部分也就对应着将数组数据分为 bucket_size 部分，遍历数组数据将其分配到各个部分同时对各个部分排序。最后遍历各个部分得到排序后的数据。
桶排序的时间复杂度为 \(\Theta(n)\)

• 两层的 SkipList
  对于包含 n 个元素，只有两层的 SkipList，时间消耗为 \(T(n) = |L_1| + \frac{n}{|L_1|} \quad 当|L_1| = \frac{n}{|L_1|}时，取到最小值，即 |L_1|=\sqrt{n}，所以 T(n) = 2\sqrt{n}\)
  
• 三层的 SkipList
  三层 SkipList，因为每层最多需要遍历 \(\sqrt[3]{n}\) 个元素， 所以时间消耗为 \(T(n) = 3\sqrt[3]{n}\)
  
• \(log_2n\) 层的 SkipList
  当 SkipList 取 \(log_2n\) 层时，SkipList 最优。此时时间消耗为 \(T(n) = log_2n\sqrt[log_2n]{n} = 2log_2n\)
  

对每层来说，一个节点会向上增长的概率为 \(\frac{1}{2}\) ，则第 m 层向上增长的概率为 \(\frac{1}{2^m}\)
底层一共有 n 个元素，上升到 m 层时，m 层元素数目的期望为 \(E[C_m] = n\frac{1}{2^m} = \frac{n}{2^m}\)
令 \(E[C_m] \leq 1 则 \frac{n}{2^m} \leq 1 即 n \leq 2^m 所以 lgn \leq m\)
即 当 \(m \geq lgn\) 时，m 层的元素数目小于 1，即 m 层不存在元素了。

• 插入节点
  插入新节点的时候随机一个 1 到 100 的数字 randomV，如果 randomV 大于 50，则将这个数提升到更高层的表中，对这个节点继续执行前面的随机操作。
  
• 删除节点
  删除节点的时候，如果该节点在多层中出现，则直接将其在出现的层中都删除掉。
  

缺点：

• 如果关键字的全域 U 很大时，由于内存大小限制，无法在计算机中存储 U 中所有元素。
  
• 如果关键字的全域 U 和实际关键字集合相差很大时，存储 U 中所有元素会造成很多空间浪费。
  

散列函数 h 将关键字 k 散列到一个小范围域内，从而减弱直接寻址表缺点的影响。

缺点：
有可能不同的关键字会被 h 函数散列到同一槽上。这种情况被称为发生了碰撞。

在开放寻址法中，所有元素都存储在散列表中。即，每个表项中或存储一个元素，或存储 NIL 值表示不存储任何元素。

给定 n 个关键字，构造一个静态的 hash 表，该表的大小 \(m=O(n)\) ，在最坏的情况下，查询某个关键字的时间复杂度为 \(O(1)\) ，构造出满足这些条件的哈希被称为完全哈希或完美哈希 Perfect Hashing。
构造完美哈希的一种方法是使用两级哈希，并且每一级哈希都为全域哈希。要满足完美哈希就需要第二级全域哈希不会造成冲突。设 \(n_i\) 个关键字被哈希到一级哈希表的第 i 个槽内，在二级哈希表中使用 \(m_i = n_i^2\) 个空间来存储这 \(n_i\) 个元素，则可以使二级哈希不会造成冲突。

• 证明 1：二级全域哈希不会造成冲突
  

  \begin{align} &随机变量 X 表示哈希产生冲突 \nonumber \\ &E[X] = P\{X\} = \frac{n_i(n_i-1)}{2} \frac{1}{n_i^2} = \frac{1-1/n_i}{2} < \frac{1}{2} \nonumber \\ &依据马尔可夫不等式可得： \nonumber \\ &P\{X \geq t\} \leq \frac{E[X]}{t} \nonumber \\ &P\{X \geq 1\} \leq \frac{1/2}{1} \nonumber \\ &P\{X \geq 1\} \leq \frac{1}{2} \nonumber \\ \end{align}

• 证明 2：二级哈希的存储空间复杂度为 \(O(n)\)
  取第一级 hash 表的大小 \(m=n\) ，随机变量 \(n_i\) 表示哈希到第 i 个槽的关键字的数目，在二级哈希表中槽的个数 \(m_i=n_i^2\) 则：
  

  \begin{align} &E[totalStorage] = n + E[\sum_{i=0}^{m-1}\theta(n_i^2)] = O(n) \nonumber \end{align}

HashTable 相关算法的实现：
AlgorithmIntroduce/Code_Hash.lua

遍历 查找 最大关键字元素和最小关键字元素 前驱和后继 插入和删除
具体实现可以参考如下文件：
AlgorithmIntroduce/Code_BST.lua

随机二叉查找树高度的期望值为 \(log_2n\)

• 证明：
  step1- 证明 Jensens 不等式
  \(f(E[X]) \leq E[f(X)] \quad f(X)为凹函数。\)
  step2- 不直接分析 BST 的高度随机变量 \(X_n\) ,而是分析 \(X_n\) 的凹函数，这里分析的是 \(Y_n = 2^{X_n} \, 即 X_n 的指数函数\)
  step3- 证明 \(E[Y_n] = O(n^3)\)
  step4- 证明结论
  

  \begin{align} &2^{E[X_n]} \leq E[2^{X_n}] = E[Y_n] = O(n^3) \nonumber \\ &对上面的公式两边取对数可得: \nonumber \\ &E[X_n] \leq log_2O(n^3) = 3log_2n+O(1) \nonumber \\ \end{align}

包含 n 个关键字(内节点)的红黑树，它的高度满足 \(h \leq 2log_2(n+1) = O(log_2n)\)

• 证明
  将每个红节点并入它的黑色父节点中，会形成一个 2-3-4 树。
  

  1. 2-3-4 树的每一个内节点中包含 2-4 个子节点
     
  2. 2-3-4 树的所有叶子节点有相同的深度，该深度等于叶子节点的黑高度
     

  假设 生成的该 2-3-4 树的高度为 \(h'\) ，平衡二叉树外节点的个数比所有内节点个数多 1，所以，原来红黑树的外节点数为 \(n+1\) ，所以，该 2-3-4 树的叶子节点的个数 \(leaves = n+1\) 。
  

  \begin{align} &而叶子节点的个数满足下面不等式： \nonumber \\ &2^{h'} \leq leaves \leq 4^{h'} \nonumber \\ &2^{h'} \leq n+1 \nonumber \\ &h' \leq log_2(n+1) \nonumber \\ &h \leq 2h' \leq 2log_2(n+1) \nonumber \\ \end{align}

• case1 x 的兄弟 w 是红色的
  
• case2 x 的兄弟 w 是黑色的，而且 w 的两个孩子都是黑色的
  
• case3 x 的兄弟 w 是黑色的，w 的左孩子是红色的，右孩子是黑色的
  
• case4 x 的兄弟 w 是黑色的，而且 w 的右孩子是红色的
  

具体实现参考下面文件：
AlgorithmIntroduce/Code_RBT.lua

用扩展的红黑树来实现动态顺序统计，OS-Select 和 OS-Rank 的时间复杂度为 \(lg(n)\) .

秩 即为元素在序列中的顺序值。
因为这样做的话，添加或删除节点，需要修改很多节点的秩，这样维护红黑树的时间复杂度为 \(O(n)\) 。

数据结构扩展的 4 个步骤：

1. 选择基础数据结构
   
2. 确定要在基础数据结构中添加哪些信息
   
3. 验证可用基础数据结构上的基本修改操作来维护这些添加的信息
   
4. 设计新的操作。
   

以动态顺序统计为例来说，整个过程为以下步骤：

1. 选择红黑树来作为基础数据结构
   
2. 在基础数据结构中添加额外的 size[x] 信息，size 为以 x 节点为根的子树的节点数目
   
3. 插入-删除-节点旋转等操作对新加的 size 信息是可维护的。
   [重新实现这些修改操作，来支持对 size 信息的维护]
   
4. 设计新的操作：OS-Select 和 OS-Rank。
   

以区间树为例来说，整个过程为以下步骤：

1. 选择红黑树来作为基础数据结构。在基础数据结构中存储区间信息，并以区间的低端点作为节点的关键字
   
2. 在基础数据结构中添加额外的 max[x]信息，max[x]为以 x 节点为根的子树中端点最大的数值。
   
3. 重新实现这些修改操作，来支持对 max 信息的维护
   
4. 设计新的操作：Interval_Search(T, i)
   

• 一个全局最优解可以通过局部最优选择来达到。换句话说就是，当我们考虑做选择时，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。
  
• 在贪心算法中，我们做的总是当前看似最佳的选择，然后再解决选择之后所出现的子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待做出的选择或子问题的解。因此，贪心策略通常是自顶先下，一个一个地做出贪心选择，不断地将给定的问题实例归约为更小的问题。
  

通过求总的时间消耗 \(C\) ，然后除以操作数目 \(n\) 得出每个操作的平摊代价。
\(c = \frac{C}{n}\)

通过为不同的操作收取不同的费用，操作没有花费掉的费用存入银行，用总价格 \(P\) 减去银行的存款 \(B\) 然后再除以总的操作数 $n$。
\(总的平摊代价 C = P-B\)
\(每个操作的平均平摊代价 c = \frac{P-B}{n}\)
\(在 n 个操作中，令第 i 个操作的实际代价为 c_i,第 i 个操作的平摊代价为\widehat{c_i},则对于 n 个操作的所有序列需要满足 \sum_{i=1}^n\widehat{c_i} \geq \sum_{i=1}^nc_i, 这样总的平摊代价就是实际代价的一个上界。\)

势能方法中不是将已预付的工作作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”或“势”，它在需要时可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。
\(\widehat{c_i} = c_i + \Phi(D_i) - \Phi(D_{i-1})\)
\(\sum_{i=1}^n\widehat{c_i} = \sum_{i=1}^n(c_i + \Phi(D_i) - \Phi(D_{i-1})) = \sum_{i=1}^nc_i + \Phi(D_i) - \Phi(D_0)\)
如果能定义一个势能函数 \(\Phi\) 使得 \(\Phi(D_i) \geq \Phi(D_0)\) ,则总的平摊代价就是实际代价的一个上界。

• 图的数学描述
  G=(V,E) 表示拥有顶点集合 V 和边集合 E 的图 G。|V|表示顶点的数量，|E|表示边的数量
  
• 邻接矩阵
  空间复杂度为 \(|V|^2\)
  矩阵中所存储的数值，可用来表示图中边的权值
  
• 邻接表
  如果 G 是一个有向图，则所有邻接表的长度之和为|E|。如果 G 是一个无向图，则所有邻接表的长度之和为 2|E|。不论是有向图还是无向图，邻接表的空间复杂度为 \(O(V+E)\)
  当 E 远小于 \(|V|^2\) 时，采用邻接表更省空间。
  邻接表中存储的节点可以携带权值，表示当前顶点到该节点的权值大小。
  邻接表在需要确定图中边(u,v)是否存在，只能在邻接表 Adj[u]中搜索是否存在 v。
  

广度优先搜索的时间复杂度为 \(O(V+E)\)
搜索过程中，通过给节点上色来避免节点重复被访问
广度优先搜索需要利用队列来保证搜索过程基于广度优先。

深度优先搜索的时间复杂度为 \(O(V+E)\)
搜索过程中，通过给节点上色来避免节点重复被访问

最小生成树可以用来解决整体耗费最小的问题。如下面所述问题

1. 旅游路线选择
   N 个旅游地点都得去，但是要总路费最小。
   
2. 多个城市之间电缆架设等问题
   N 个城市都得连接，但是要总的电缆使用最少。
   

单源最短路径 Dijkstra 的思路为 维护一个集合 \(S\) ,让该集合内的所有元素到源点 \(s\) 的距离为最短距离, 然后不断扩大这个集合让其包含所有的顶点。为了保证新加入集合 \(S\) 的元素符合条件，必须取 \(V-S\) 中距离 \(S\) 最小的元素。具体操作是，从源点开始对图进行广度优先遍历，判断当前顶点的邻接顶点到源点的距离是否比之前记录的距离短，如果是则更新邻接顶点的父节点和其到源点的距离，选出离源点最近的节点进行下次循环操作。
Dijkstra_SingleSourceShortestPath 的时间复杂度如下：

在概率论中把符合下面三个特点的试验叫做随机试验：

1. 一次试验结果的随机性，即进行一次试验之前无法确定哪一个结果会出现。
   
2. 全体测试结果的可知性，即每次试验的可能结果不止一个，并且能事先明确试验的所有可能结果。
   
3. 可重复性，即可以在同一条件下重复进行试验。
   

设 E 是一个随机试验，其样本空间为 S，若对每一个样本点 \(e \in S\) ，都有唯一确定的实数 X(e) 与之对应，则称 S 上的实值函数 X(e) 是一个随机变量（简记为 X）。

• 实例一
  随机投掷一枚硬币，可能的结果有正面朝上 ，反面朝上两种 ，若定义 X 为投掷一枚硬币时朝上的面 ， 则 X 为一随机变量，当正面朝上时，X 取值 1；当反面朝上时，X 取值 0。
  
• 实例二
  又如，掷一颗骰子，它的所有可能结果是出现 1 点、2 点、3 点、4 点、5 点和 6 点 ，若定义 X 为掷一颗骰子时出现的点数，则 X 为一随机变量，出现 1，2，3，4，5，6 点时 X 分别取值 1，2，3，4，5，6。
  

给定一个样本空间 S 和事件 A，那么事件 A 对应的指示器随机变量：

离散型随机变量的一切可能的取值 xi 与对应的概率 Pi(=xi)之积的和称为该离散型随机变量的数学期望（设级数绝对收敛），记为 E（x）。
设连续性随机变量 X 的概率密度函数为 f(x)，若积分绝对收敛，则称积分的值为随机变量的数学期望，记为 E(X)。
http://www.zhihujingxuan.com/19043.html