advanced algorithm and data structure note

算法笔记

Lecture 1

1.Maximum Subarray(连续的最大子集（暴力和分治法）)

a.暴力（brute force）

（1）创建所有子集

（2）分别计算所有子集的和

（3）寻找子集中和最大的一组子集

b.分治法（O(nlogn)）

（1）将数列分成两个部分，并且不停的二分寻找

（2）寻找左右两部分的最大值，并且从中间开始向两边获取最大值，中间寻找的区间为左侧最大的下标以及右侧最大下标

（3）比较左右两部分以及中间获得的最大值，并返回三个中最大的一个，不断的从二分中向上回溯

CLRS 在讲解分治问题时将这一问题作为例题。分治算法在计算 A[low…high] 的最大子数组之和时，将其分为 A[low…mid] 和 A[mid+1…high] 两个数组分别计算。在合并时，考虑 A[low…high] 的最大子数组必为以下三种情况之一：

• 最大子数组完全落在 A[low…mid]中。

• 最大子数组完全落在 A[mid+1…high] 中。

• 最大子数组左右端点跨过中间点 mid]。

前两种情况只需递归调用即可；第三种情况需要单独处理。需要从 mid 开始分别向两个方向不断求和，分别计算出两个方向的最大值（两者的端点其中之一均为中间点），求和就得到第三种情况的最大值。

取三种情况计算出的最大值的最大者为 A[low…high] 的最大子数组之和。

2.时间复杂度（通常计算最坏情况下的，且n倾向于无限大）

a. T(n)表示时间频度， f(n)代表代码的执行次数

b. O(n)表示时间复杂度，表示呈现的规律，与T(n)相差常数c, O(n)=c*T(n)，一般是算法的上界复杂度，即最坏情况下的复杂度。f(n) = O(g(n))，存在正常数c、n、n0，当n>n0的时，对于任意的f（n）对符合0<= f（n）<= c.g（n）。

c. Ω(n)当函数的大小只有下界，没有明确的上界的时候，可以使用大Ω表示法，一般用与描述算法的 最优复杂度 。f(n）= Ω(g(n))，对于任意的f（n）对符合0<= c.g（n）<= f（n）。

d.  θ(n)为确界. 函数既有上界，同时也有下界，即最坏和最优情况都有规定。f(n) = O(g(n)) 并且 f(n）= Ω(g(n)) 时，才有 f(n) = θ(g(n))。

e. o(n), 0<= f（n）< c.g（n）, lower than g(n)

f. ω(n) , 0<= c.g（n）< f（n）, faster than g(n)。

示例：

查找： 如果要找的数在第一个，则为最优情况则为Ω(1)， 如果要找的数在最后则为最坏情况，则为O(n)， 如果数组只有一个数，最好为Ω(1)，最坏为O(1)， 则可以说其为θ(1)

Lecture2

1.递归方程的时间复杂度

解决递归方程的三种方法。

- 代入法：对复杂类进行猜测，验证并通过递归推导出参数

- 递归树法。用函数的所有递归调用画一棵树，并将每个节点的所有步骤加起来

- 主方法。一个一般的定理，根据方程的形式给你复杂度等级

主定理方法：

主定理：

Lecture 3

1. Binary Search Tree(二分查找树)

特点：

每个节点的左孩子都比其小，并且其左边的所有后代都要比其小

每个节点的右孩子都要比其大，并且右边的所有后代都要比起大

操作：

a.查找（x为当前节点， 查找的节点为k）

1. 如果 x值为空，则 k 不在 BST 中；

2. 比较 x 和 k的值；

3. 如果值相同x.value = k.value，则找到了指定节点 k；

4. 如果 k 的值小于 x，那么如果 k 存在，必然在 x的左子树中。回到第 1 步，进入到x的左孩子中，即将x的左孩子作为当前节点x；

5. 如果 k 的值大于 x，那么如果 k 存在，必然在 x 的右子树中。回到第 1 步，将 x 的右孩子作为 当前节点x；

时间复杂度：最佳情况是 O(log­n)，而最坏情况是 O(n)。

最佳情况是只需要寻找树的一半，每一层都是一半的子树，因此寻找的时间复杂度为树的高度，树的高度：2^h=n h=log2n(n为树的节点个数)

最坏情况是按照递增顺序插入元素，即呈现线性向下。

b. 中序遍历（O(n)）

概念：先访问当前节点的左孩子在访问当前节点，最后是右孩子。当访问其孩子还拥有子树时，需要先完成子树的中序遍历。

中序遍历是从当前节点（节点 c）的左孩子开始访问，再访问当前节点，最后是其右节点。开始时，节点 c 为 BST 的根节点。算法如下：

1. 访问节点 c 的左孩子；

2. 对节点 c 重复第 1 步；

3. 对节点 c 的右孩子重复第 1 步。

则图中树的遍历结果为：5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200

c.最小最大(O(logn))

二叉搜索树的最小值为树的最右侧子节点， 最大值为树的最左侧子节点。

d.插入（最坏O(n),最好（O(logn）类似查找操作）（从根节点开始，首先当前节点等于根节点）

1. 如果根节点为空，则将插入的值作为根节点

2. 如果插入节点n的值等于当前节点x的值，则说明用户在试图插入一个重复的节点。

3. 如果插入节点的值n小于根节点的值，则说明节点 n 一定是在节点 x的左子树中。否则，则在其右子树中。

4.若小于根节点，则将当前节点从根节点转为根节点的左孩子，并将插入节点与当前节点比较。如大于根节点，则将当前节点转为当前节点的右孩子，并继续比较。

e.删除(最坏O(n),最好（O(logn）)：

• 情况 1：如果删除的节点没有右孩子，那么就选择它的左孩子来代替原来的节点。

二叉查找树的性质保证了被删除节点的左子树必然符合二叉查找树的性质。因此左子树的值要么都大于，要么都小于被删除节点的父节点的值，这取决于被删除节点是左孩子还是右孩子。因此用被删除节点的左子树来替代被删除节点，是完全符合二叉搜索树的性质的。

• 情况 2：如果被删除节点的右孩子没有左孩子，那么这个右孩子被用来替换被删除节点。

因为被删除节点的右孩子都大于被删除节点左子树的所有节点，同时也大于或小于被删除节点的父节点，这同样取决于被删除节点是左孩子还是右孩子。因此，用右孩子来替换被删除节点，符合二叉查找树的性质。

• 情况 3：如果被删除节点的右孩子有左孩子，用被删除节点的右子树中最小值的节点来替换。

Lecture4

1.Red -Black Tree(RBT)(O(logn))

定义：自平衡的二叉搜索树

要求：

1. 每个节点必须有颜色：黑色或者红色

2. 根节点颜色必须是黑色

3. 红色节点的子节点必须是黑色的

4. 从任何节点到其叶子节点（即空节点NIL）的路径中，出现的黑色节点的数量一样。 （每一条路径上的黑色节点数量一样）

5. 红黑树的高度最高为（2*log2(n+1)）

6. 搜索的复杂度为O（logn）,插入删除与二叉搜索树一样最坏O(n),最好（O(logn）

失去平衡：

**情况1：LL（**插入的节点是父亲的左孩子，且其父亲是爷爷的左子节点），插入的节点后，形成左侧一条线的情况

将插入节点的父亲设为黑色，将插入节点的爷爷设为红色，右旋

• 将p设为黑色

• 将PP设为红色

• 对PP进行右旋

情况2：LR(插入的节点是父亲的右孩子，且其父亲是爷爷的左子节点)

（1）先对插入节点的父亲进行左旋，将插入节点作为父亲，并将其父亲变为左子节点，转换为LL型，在将其当做LL型对待，将其右旋恢复平衡。

情况3：RR(插入的节点是父亲的右孩子，且其父亲是爷爷的右子节点)。插入的节点后，形成右侧一条线的情况。

与LL相反

将插入节点的爷爷节点左旋，并将其变为红色，将插入节点的父亲节点变为黑色。

情况4： RL(插入的节点是父亲的右孩子，且其父亲是爷爷的右子节点)。

与LR相反

先对插入节点的父亲进行右旋，将插入节点作为父亲，并将其父亲变为右子节点，转换为RR型，在将其当做RR型对待，将其左旋恢复平衡。

操作：

a.插入(O(logn))：

（1）红黑树为空，直接插入节点，并将其标记为黑色。

（2）红黑树不为空，则在根据二叉搜索树的性质，在正确的叶子节点上插入节点，并将其标记为红色。重新检查红黑树属性。如果其父节点颜色为黑色，则满足红黑树条件。如果其父节点为红色，需要重新调整。

情况不同：

**情况1：**如果插入的红色节点的父亲节点为红色，且其父亲节点有红色颜色的兄弟，且其爷爷节点为根节点，则可以将插入节点的父亲与兄弟节点上色为黑色。如果其爷爷不是根节点，则需要把爷爷转换为红色节点。并将爷爷节点开始当做插入的红色节点，重复此过程直到满足红黑树。

**情况2.**如果插入的红色节点的父亲节点为红色，且其父亲节点的兄弟节点为黑色或者没有兄弟节点，考虑失去平衡的四种情况，对其进项相应的左右旋。

b.删除

删除节点后，用于替换被删除节点的情况

（1）如果删除节点没有子节点，则直接删除

（2）如果删除节点只有一个子节点，用子节点替换删除的节点

（3）如果有两个子节点，则用删除节点的右子树中最小的节点替换删除节点

替换子节点的情况（（1）自己是红色的，直接顶替并且变为删除节点的颜色。（2）自己节点是黑色的，通过旋转以及重新上色，将兄弟节点或者兄弟节点的子树中的节点转为自己（3）兄弟都帮忙不了的，将兄弟节点转为红色，并将替换节点转为其父节点重新进行替换节点调整：）

情况1：替换子节点为红色节点

直接替换，并将其设置为被删除节点的颜色

情况2：替换节点为黑色，且其为其父节点的左子节点（需要重新保持红黑树平衡）。

场景 2.1：替换节点的兄弟节点是红色。因此其父亲节点一定为黑色。删除黑色节点，左子树中黑色节点数减少一个，可以通过一些操作，达到间接借用红色的兄弟节点来补充左子树中黑色节点数。从而保证红黑树继续平衡。

处理：替换节点的父节点 P 设置红色、兄弟节点 S 设置成黑色，再对节点 P 左旋操作，从而使得替换节点的兄弟节点变为父节点。变成场景 2.4。

场景 2.2：替换节点的兄弟节点是黑色（因此父节点与子节点的颜色不确定）且兄弟节点的右子节点是红色、左子节点任意颜色。同样是间接借用兄弟节点的红色右子节点补充到左子树中，达到红黑树的平衡。

处理：替换节点的兄弟节点 S 设置成父节点P的颜色，兄弟节点的右子节点 SR 设置为黑色，父节点P设置为黑色，再对节点 P 左旋操作。此时节点R替换到删除节点位置之后，红黑树重新达到平衡状态。

场景 2.3：替换节点的兄弟节点是黑色且兄弟节点的左子节点是红色，右子节点是黑色。

处理：替换节点的兄弟节点 S 设置成红色，兄弟节点的左子节点 SL 设置为黑色，再对节点 S 右旋操作，转换到了场景 2.2，再进行场景 2.2 的操作。

场景 2.4：替换结点的兄弟结点的子结点都为黑结点，即兄弟节点中没有红色节点

处理：替换节点的兄弟节点 S 设置成红色，并将替换节点的父亲节点作为新的替换节点，重新考虑上述的替换节点的4种情况，自底向上。

情况3：替换节点为黑色，且其为其父节点的右子节点（需要重新保持红黑树平衡）。场景2的镜像。

场景 3.1：替换节点的兄弟节点是红色。因此其父亲节点一定为黑色。删除黑色节点，右子树中黑色节点数减少一个，可以通过一些操作，达到间接借用红色的兄弟节点来补充右子树中黑色节点数。从而保证红黑树继续平衡。

处理：替换节点的父节点 P 设置红色、兄弟节点 S 设置成黑色，再对父亲节点 P 右旋操作，从而使得替换节点的兄弟节点变为父节点。变成场景 3.4。

场景 3.2：替换节点的兄弟节点是黑色（因此父节点与子节点的颜色不确定）且兄弟节点的左子节点是红色、右子节点任意颜色。同样是间接借用兄弟节点的红色右子节点补充到右子树中，达到红黑树的平衡。

处理：替换节点的兄弟节点 S 设置成父节点 P 的颜色，兄弟节点的左子节点 SL 设置为黑色，父节点P 设置为黑色，再对节点 P 右旋操作。此时节点 R 替换到删除节点位置之后，红黑树重新达到平衡状态。

场景 3.3：替换节点的兄弟节点是黑色且兄弟节点的右子节点是红色、左子节点为黑色。

处理：替换节点的兄弟节点 S 设置成红色，兄弟节点的左子节点 SR设置为黑色，再对节点 S 左旋操作，转换到了场景 3.2，再进行场景 3.2 的操作。

场景 3.4：替换结点的兄弟结点的子结点都为黑结点，即兄弟节点中没有红色节点

处理：替换节点的兄弟节点 S 设置成红色，并将替换节点的父亲节点作为新的替换节点，重新考虑上述的替换节点的4种情况，自底向上。

Lecture5

1.分治

（1）将问题分解为子问题

（2）子问题可能会反复用到

2．动态规划

可以采用动态规划来求解的问题需要具有以下两个主要特征：

1）**重叠子问题（Overlapping Subproblems）：**有些子问题会被重复计算多次。

2）**最优子结构（Optimal Substructure）：**问题的最优解可以从某个子问题的最优解中获得。

3）在第一次计算过子问题后，记住该问题以后反复利用。

动态规划计算的方法：

（1）创建一个已经计算过答案的子问题的表，表中包含子问题以及对应的答案

（2）在遇到子问题是首先查找表中是否存在相应的答案

（3）如果不是重复的子问题，表中没有相应答案，则计算该子问题并将其记录到表格中。

动态规划适用的场景：

1.最优子结构

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.无后效性

无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

3.子问题重叠

子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

所熟知的斐波那契数列的递推式就是动态规划的一种体现

3.钢条问题

**问题：**知道每个长度n的钢条对应的价格，现在讲一个长度为n的钢条进行切割，求最后的利益最大化。

**思想：**切两刀，一段长度为i， 另一段为n-i， 固定售出长度为i的段，价格为Pi，另一段调用之前切割的相应长度的利润。取最大值（i=1 to n的不同的尝试）

例如长度为4英寸的钢条的最大利益：

比如切割成（1，3）两段，则最大利益为长度为1的钢条的利益+长度为3时的钢条的最大利益。

因此，需要计算长度为3时候的钢条的最大利益。长度为3时候的最大利益也需要一次次的通过类似方法递归试验。

比如切割成（2，2）两段，则最大利益为长度为2时候的利益，加上，长度为2时候的最大利益。

**动态规划中：**将每次的得出的对应长度的钢条的最大利益都存入对应的数组中，如遇到计算过的长度的钢条，则直接调用数组中的答案。

动态规划有两种方法：自顶向下，自底向上（自顶向下与自底向上算法具有相同的渐进运行时间!(）

自顶向下（从当前长度开始计算，不断推更小的）：

例如：求4英寸的长度，会先从r4开始往前推r1

//生成对应长度钢条的最大利益的矩阵，并初始化

mem-cut-rod(p, n)

1  let r[0…n] be a new array

2  for i=0 to n

3    r[i] = -∞

4  return mem-cut-rod-aux(p, n, r)

 

//计算每次长度下的钢条的最大利益，并将其对应的最大利益存入数组

mem-cut-rod-aux(p, n, r)

//如果数组中存在则说明有该长度下的解，直接返回

1  if r[n] >= 0

2    return r[n]

 

//长度为0的钢条没有价值

3  if n == 0

4    q = 0

 

//正常计算钢条的长度

5  else 

6    q = -∞

7    for i=1 to n

8      q = max(q, p[i] + mem-cut-rod-aux(p, n-i, r))

9  r[n] = q

10  return q

自底向上（从最小的情况开始算，不断向上推）：

例如求4英寸的长度，会从r1开始逐步记录，逐渐向上推到r4

bottom-up-cut-rod(p, n)
1    let r[0…n] be a new array
2    r[0] = 0
3    for j=1 to n
4        q = -∞
5        for i=1 to j
6            q = max(q, p[i] + r[j-i])
7        r[j] = q
8    return r[n]

复杂度分析：

1.直接递归，不记录每次的最大利益 T(n)=2^n

每次都需要重新计算之前的，伪代码：

Cut-Rod(p, n)
1    if n==0
2        return 0
3    q = -∞
4    for i = 1 to n
5        q = max(q, p[i] + Cut-Rod(p, n-i))
6    return q

下图显示了n=4时的调用过程CutRob(p, n)对i=1,2,…,n调用CutRob( p,n-i )，等价于对j=0,1,…,n-1调用CutRob( p, j )，该递归展开时，所做的工作量会爆炸性增长。

第一项 ‘1’ 表示函数的第一次调用（递归调用树的根节点），T( j )为调用cutrob(p, n-i)所产生的所有调用次数。T(n) = 2^n。即该算法的运行时间为n的指数函数。

2. 动态规划的复杂度：

自底向上：!

两层循环嵌套，内层的循环次数为等差数列，因此时间为

自顶向下：

对于求解过的问题直接返回O(1),对于子问题只求解一次，因此n长度的，求解规模为n个子问题，求解迭代为n次，因此时间也为

Lecture6

1.图论

a. 图的表达形式

（1）列表

形式：连接的边（i，j）两端点

将所有的连接的边存入列表中

例如：[(0, 1), (0, 3), (1, 4), (2, 0), (2, 3), (3, 0), (3, 1), (3, 4), (4, 1), (4, 2)]

（2）邻接列表

形式：（i,j）表示为顶点i ->[连接的边的顶点j]

提取顶点i，并将连接的边的顶点j存入，用以表示连接的边（i ，j）

0 -> [1,3]

1 -> [4]

2 -> [0,3]

（3）邻接矩阵

形式：构建顶点数量*顶点数量大小的矩阵，如果连接为1， 不连接为0，自身到自身不闭环（不连接）

b.空间复杂度

邻接列表的空间复杂度为：O(V + E)

为顶点的个数+边的条数

邻接矩阵的空间复杂度为： O(V^2)

邻接矩阵的构成是顶点*顶点，因此复杂度为顶点个数v*v

使用邻接列表还是邻接矩阵取决于边的数量：

（1）如果连接的边的数量接近于顶点数*顶点数（v^2）即全部连接的情况，则使用邻接矩阵

（2）如果连接的边的数量远小于顶点数*顶点数（v^2）即全部连接的情况，则使用邻接列表

c.最短路径（可以进行动态规划求解）

（1）可以将选择顶点i->j的最短路径，转为选择中间节点k进行子问题切割

（2）在处理i->k的子问题中又存在子问题，例如包含v-w

（3）可能存在重复子问题，例如i->k中存在v-w子问题，k->j中也可能存在此问题

d.最长路径：寻找两个顶点间的最长距离（不能包含闭环）

不能采用动态规划：可以分解为子问题，但是子问题的最优解合并后可能会闭环。

e.带权图：每条连接的边都具有其权重

当图具有权重后，可修改邻接列表和邻接矩阵使其带有权重

（1）权重图的邻接列表表示：

形式：（i,j）表示为顶点i ->[(连接的边的顶点j1，权重)，（连接的边的顶点j2，权重)]

提取顶点i，并将连接的边的顶点j以及边ij的权重存入，用以表示连接的边（i ，j）以及对应权重

0 -> [（1，1.0）1,（3，2.0）] 表示为（边（0，1），权重为1.0； 边（0，3），权重为2.0）

（2）权重图的邻接矩阵表示：

形式：构建顶点数量n*n大小的矩阵，如果连接则将连接边的权重填入，不连接则设为无穷。

（3）最短路径问题（路径的权重之和最小，路径权重为非负数）：

进行无权重图进行最短路径问题的时候，可以将路径权重都赋予1.0

方法1：单源最短路径（single-source shortest path）: 给定一个源顶点，找到他到其他所有顶点的最短路径。

Dijkstra算法就是单源最短路径（不适用于包含负权重的）时间复杂度为（O(V^2O(V^2))）

(1)松弛

原理：源顶点通过添加进来的顶点，并根据新添加的顶点延伸出去的顶点的距离小于源节点直达该延伸节点的距离，则松弛成功。

< v3,v4 >,那么我们看看路径：v1–v3–v4的长度是否比v1–v4短，其实这个已经是很明显的了，因为dis[3]代表的就是v1–v4的长度为无穷大，而v1–v3–v4的长度为：10+50=60，所以更新dis[3]的值,得到如下结果：

即 v1顶点到 v4顶点的路程即 dis[3]，通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想：通过"边"来松弛v1顶点到其余各个顶点的路程。

（2）算法原理

1.先找源节点能够直达的第一个最小的节点，将其添加入集合T。

2.观察新添加进来的节点，其向外发送的节点有哪些，将源节点到这些延展节点的距离与源节点直达这些节点的距离作比较，要是比直达更小，则更新dis

3.除了确定的最小值外（即已确定最小路径，且没有其他路径能够到达时），寻找剩余中最短距离的那个节点，并将其加入集合T，重复步骤2观察其延伸的节点，并更新dis最短距离表。

4.不断重复，知道源顶点到所有的点的最短距离都已经更细完毕

方法2：全对最短路径（all-pairs shortest path）:图中成对的顶点（即每个顶点到其他各个顶点）的最短的路径。输出的最短路径矩阵与给定的权重矩阵大小相同，将每个顶点到其他顶点的最小权重路径记录在矩阵中。

Floyd_Warshall算法就是全对最短路径算法。

1.实现

（1）构造最短距离表dist，并将不连接的设为正无穷

（2）使用中转节点k分割顶点（i，j），使得（i，j）=(i,k)+(k,j)

（3）不断选取中转节点中较小的情况。

思想原理：

通过将不同的顶点逐个作为中转节点，给图中所有的成对顶点进行松弛（即进行在直达中增加节点），将两点间的最短路径替换为松弛后的最短距离。
**

for(int k = 1; k <= n; k++)//将节点从1-n作为中转节点。

	for(int i = 1; i <= n; i++)//遍历成对顶点

   		for(int j = 1; j <= n; j++)

​      			if(e[i][j] > e[i][k]+e[k][j])

​        			e[i][j] = e[i][k]+e[k][j]

Lecture7

1.分摊分析

a.原理

将复杂度分摊到每次操作上，一个大复杂度的操作可以被分摊到很多小复杂度的操作上，对数据结构连续地实施足够多此操作，所需总成本分摊至单次操作。

平均复杂度或计算复杂度（平均/预期的复杂度）平均分布，将按照平均计算的计算各类操作（例如包含插入，搜索，删除等）

所有操作的分摊复杂度之和>=所有操作的实际复杂度之和

b.分摊分析的方法

（1）accounting method

往银行中进行存取操作都需要花手续费，当进行完存操作后，就会存在余额，因此当进行取操作时，可以使用余额抵扣取操作的手续费。因此分摊成本=实际上操作的成本+银行中的余额-支付的手续费

所有操作的分摊复杂度之和>=所有操作的实际复杂度之和

并且银行账户余额需要为非负数，因此

所以操作存入的银行余额>=为所有操作的手续费

（2）potential method

势能方法（potential method）中势能是对整个一系列操作而言的，即一些操作会增加整体势能，而一些操作会减少整体的势能**。**

数据$D_{i - 1}$经过第i个操作后，变为了数据$D_{i}$，且第i个操作的真实花费为$c_{i}$, 数据$D_{i - 1}$的势能为$\Phi(D_{i - 1})$，数据$D_{i}$的势能为$\Phi\left( D_{i} \right)$，因此第i个操作的分摊花费$\overset{\hat{}}{c_{i}}$为

$$\overset{\hat{}}{c_{i}} = c_{i} + \Phi(D_{i}) - \Phi(D_{i - 1})$$

因此所有的操作一起则为：

$$\sum_{i = 0}^{n}\overset{\hat{}}{c_{i}} = \sum_{i = 0}^{n}{(c_{i} + \Phi(D_{i}) - \Phi(D_{i - 1}))} = \sum_{i = 0}^{n}{c_{i} + \Phi(D_{n}) - \Phi(D_{0})}$$

为了平均花费的总和是真实花费总和的上界限，必须保证$\Phi(D_{n}) \geq \Phi(D_{0})$，由于不知道n的值，因此每次需要保证每个第i个操作都需要小于$\Phi(D_{0})$，因此可表示为：

$$\Phi(D_{i}) \geq \Phi(D_{0})$$

因此势能函数定义时需要满足$\Phi\left( D_{0} \right) = 0而且\Phi(D_{i}) \geq 0$

势能分析的关键在于定义势能函数。

（3）聚合方法（aggregate method）

简单计算所有k种操作的复杂度总和，分摊复杂度为复杂度总和/操作的种类

在聚集分析（Aggregrate analysis）中，对一系列（n个）操作在最坏情况下总共花费的时间称$T(n)$

因此对每个操作的平摊花费（amortized cost）为$T(n)/n$。

Lecture8

1.Priority Queue

优先队列的出队（Dequeue）操作和队列一样，都是从队首出队。但在优先队列的内部，元素的次序却是由"优先级"来决定：高优先级的元素排在队首，而低优先级的元素则排在后面。这样，优先队列的入队（Enqueue）操作就比较复杂，需要将元素根据优先级尽量排到队列前面。

a.Heap

最小堆与最大堆：

最小堆：即所有的父节点的值都小于子节点，即根节点为堆中最小值，但不在乎左右子节点的大小对比。

最大堆：即保证所以父节点的值都大于子节点，即根节点为堆中最大值，同样不在乎左右子节点的大小。

实现的功能与对应复杂度：

(1)未排序的堆

插入：θ(1)

最小值：θ(n)：

因为未排序，因此需要查找整个堆

提取：θ(n)：

找到最小值取出，因此也是寻找整个堆

(2)排序的列表

因为是排序的最小堆，因此查找最小值和提取最小值都为θ(1)，插入的话需要找到合适的位置为θ(n)

2.二叉堆

a.定义：最小二叉堆，父节点小于子节点，且每个父节点最多有2个子节点，类似二叉搜索树,且左右子节点的数量差距不超过1

隐式结构：可以将其用数组存储表示

b.功能

（1）插入：

1.将其放在二叉堆的底部，同时保证二叉堆的平衡，即注意左右子树的节点数量差异

2.将其不断与其父亲节点比较，如果其<小于父亲节点，则将其替换为父亲节点，并且不断往上比较，直到其不小于父亲节点。

复杂度为：O（logn）

因为插入的时候需要不断与其父亲节点比较，因此整个数的父亲节点即为树的高度，树的高度为logn，因此插入的复杂度为O(logn)，因为最坏的情况下需要比较到根节点。

（2）删除(取出最小节点，即取出根节点)

1.取出根节点后，用最后一个节点代替他的位置

2.取代后，进行调整，满足最小堆。比较其子节点大小，选择其中较小的那个，如果当前节点大于子结点中较小的，则将其交换。并将当前节点指向交换后的位置，继续比较，直到当前位置节点不大于其子节点。

复杂度为：O（logn）

类似插入，因为删除的时候需要从根节点不断与子节点开始比较，最坏情况下，需要从根节点比较到最后一层的子节点，因此最坏情况下比较的复杂度为树的高度，树的高度为logn，因此删除的复杂度为O(logn)，因为最坏的情况下需要比较到根节点。

Lecture9

1.各类堆中操作的复杂度

斐波那契函数的复杂度：为分摊时间

a.斐波那契堆的分摊分析

（1）potential method的势函数

势函数分析斐波那契堆的操作性能，首先我们给出势函数的表达式：

式中H表示一个斐波那契堆，t(H)表示堆中树的数目即（根链表中节点的个数），m(H)表示堆中已经被标记的节点的数目

2.斐波那契堆（好几个最小堆的结合体）

定义：斐波那契堆是一系列具有最小堆序的有根树的集合，即斐波那契堆中的每棵树均遵循最小堆性质。

头结点永远指向根链表中最小的节点即H.min

a.结构：

全部是最小堆，并且以双向链表连接；

（1）组成斐波那契堆的所有最小堆的根结点也链接形成一个双向链表，它称为斐波那契堆的根链表(root list)。

（2）每个最小堆中的每一个结点x包含一个指向它父结点的指针x.p和一个指向它某一孩子结点的指针x.child；

（3）每个最小堆的每个子节点x都将其所有孩子节点也以双向链表连接（称为x的孩子链表(child list)）。

子节点x的每一个孩子y均有指针y.left, y.right分别指向它的左兄弟和右兄弟，如果其孩子节点只有一个，没有兄弟，即孩子链表中只有一个结点，则指针y.left,y.right指向自己，即y.left=y.right=y。

（4）每个结点x具有属性：x.degree，表示自己的直接孩子的数目。

（5）每个节点具有布尔类型的属性x.mark，表示结点x自从上一次成为某一个结点的孩子后，是否失去过孩子。

（6）对于一个给定的斐波那契堆H，它有一个属性min，指向具有最小关键字的最小堆的根结点（称为斐波那契堆的最小结点(minimum node)）。

（7）consolidated heap：根链表中的每个节点（即组成斐波那契堆的所有的最小堆的根节点）的degree互相不同，则可以称为consolidated heap

(8)定义数据结构 data FibHeap = FHeap (Wheel (Key, Int, FibHeap))

例子：

FHeap◦[ (2,3,h1),(7,0,emptyW),(4,6,h2),(12,2,h3),(8,0,emptyW)◦]

第一个为节点元素，第二个代表其degree（由第三个h1的节点个数得出），h1为节点元素的子孩子的堆

第二个中，第一个表示元素是7，因为其没有子孩子构成的堆，因此，其degree为0

因为第2个和第5个最小堆的degree都为0，因此，其不是个consolidated heap

b.操作（只有取出操作影响斐波那契堆的结构）

（1）最小值

最小值为斐波那契堆的第一个最小堆的根节点

（2）插入

将要插入的结点插入根链表中，然后更新最小根节点（minNode）。

**更新的逻辑是：**若此时堆是空的，直接将minNode指向插入的节点即可；若堆非空，我们将节点插入到最小节点的左边，再重新判断最小节点。否则就往右边插入

（3）合并（UNION）

将两个斐波那契额堆的根链表合并（意味着他们的子孩子的链表也会同步带来），因此重新需要计算斐波那契堆的大小。并且需要重新比较两个斐波那契堆中原来的最小值节点，将两个中更小的设置为合并后的斐波那契堆的头结点以及最小结点。

（4）取出最小值节点（取出后，都要重新计算degree，让其consolidated）

1.如果最小节点的子节点只有一个，则直接将其移入根链表中最小节点的左侧，将最小节点删除完成删除。

2.首先把最小节点的所有直接子节点（儿子节点，不包含孙子节点，但孙子节点继续挂载在儿子节点下）移动到根链表中，移动到根链表中最小节点的左边；接着从根链表中删除最小节点。

3.同一层的兄弟节点需要双向链表连接，子节点用单向指向。

3.合并度数（degree）相同的节点

将根链表中度数相同的节点进行合并。将两个度数相同的节点中较大的那个从根链表中移除，挂载到较小的那个节点上，成为其子节点（并将那个较大数值的节点的孙子节点等直接依附在该节点上挂过来）。

举例：

节点23与节点7的度数为0，需要合并。合并时，比较它们数据的大小，显然7小于23，因此将23挂到7下作为子节点：

过程：（存储degree 的数组中，数组下标代表degree，该下标存储的是节点，因为同样degree的会合并，因此下标不变，但是该下标存储代表的节点需要更新）

1.首先将步骤二完成后，将删除节点的右侧节点暂时设为最小节点。

2.从当前假设的最小结点开始向根链表的右侧遍历，如果遇到的节点的degree是新的degree则在数组中记录，右侧遍历完后，从左侧第一个开始遍历

3.当遍历到一个节点，发现其degree在数组中存在，意味着其需要合并。对其和与其有一样degree的节点进行合并操作。

4.在完成合并操作后，意味着节点的degree出现增加，则将重新计算的degree继续去与记录的数组比较（新的则记录，存在即去做合并操作）

5.直到遍历完整个根链表

举例

我们从临时最小根节点（17）开始从左往右遍历根链表。第一轮，节点17的度数为1，而数组中下标为1的位置为空，因此，直接将节点的指针（引用）存放到数组的1号位置：

接着遍历到节点24，其度数为2，2号位置也是空的，直接将节点24放到2号位置：

下一轮遍历需要回到链表的头部，即到了节点23，以其度数为下标的位置是空的，操作同上：

再接下来是节点7，注意其度数为0，而数组中0号位置已经有了节点23，这说明它们的度数都为0，需要合并。合并时，比较它们数据的大小，显然7小于23，因此将23挂到7下作为子节点：

注意，在合并后节点7的度数加了1，变为了1，需要继续判断数组的1号位置，1号位置存放的是节点17，因此需要继续合并节点7和节点17。再之后的工作就和上述一致了，这里就不在一一赘述了，直接给出每步操作后的图：

Lecture10

密码学中的算法（Algorithms in Cryptography）

1.加密算法

**问题：**防止窃听，和不安全的频道

解决方案：（1）发送加密信息 （2）使用密钥

a.非对称加密算法

**定义：**公钥加密，私钥解密

特点：加密解密速度没有对称加密解密的速度快

(1) 信息加密

收信者是唯一能够解开加密信息的人，因此收信者手里的必须是私钥。发信者手里的是公钥，其它人知道公钥没有关系，因为其它人发来的信息对收信者没有意义。

**(2)**安全性（通常）是基于硬度假设的（即取决于其算法和密钥的复杂度）

非对称密钥的大小：

特点：

（1）不是所有的钥匙都能在钥匙空间里找到

（2）有些攻击比暴力攻击更好，取决于方案

（3）对于RSA算法：整数因子化的一般数域筛子

(复杂度为：O(exp(($\sqrt[3]{\frac{64}{9}} + o(1)){(In\ N)}^{1/3}$ ${(In\ In\ N)}^{2/3})))$

（4）为了保持与2^128相当，N是2048或4096位

算法例子（RSA,EIGamal，Pailler）：

（1）RSA(加密是求"E次方的mod N";解密是求"D次方的mod N")

算法过程：

a.加密

E是加密（Encryption）的首字母，N是数字（Number）的首字母

RSA加密是对明文的E次方后除以N后求余数的过程。

b.解密

对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥：

c.生成密钥对

举例：

假设：p ＝ 17，q ＝ 19，

则：

（1）求N：N ＝ p ＊ q ＝ 323；

（2）求L：L ＝ lcm（p－1， q－1）＝ lcm(16，18） ＝ 144，144为16和18对最小公倍数；

（3）求E：1 < E < L ，gcd（E，L）=1，即1 < E < 144，gcd（E，144） ＝ 1，E和144互为质数，E = 5显然满足上述2个条件，故E ＝ 5，此时公钥= (E，N）＝（5，323）；

（4）求D：求D也必须满足2个条件：1 < D < L，E＊D mod L ＝ 1，即1 < D < 144，5 ＊ D mod 144 ＝ 1，显然当D＝ 29 时满足上述两个条件。1 < 29 < 144，5＊29 mod 144 ＝ 145 mod 144 ＝ 1，此时私钥＝（D，N）＝（29，323）；

（5）加密：准备的明文必须是小于N的数，因为加密或者解密都要 mod N，其结果必须小于N。

假设明文 ＝ 123，则 密文＝（123的5次方）mod 323=225

（6）解密：明文＝（225的29次方）mod 323 =123，所以解密后的明文为123。

安全性：

RSA密钥长度随着保密级别提高，增加很快（长度越长，安全性越高）。

b.对称加密

定义：就是加、解密使用的同是一串密钥，所以被称做对称加密。对称加密只有一个密钥作为私钥。

破坏的方法：

（1）找到密码中的弱点

（2）猜测给定例子的密钥

a.密钥都是k位（例如AES算法的密钥是128位）

b.所有密钥的可能性是一致的

c. 所有的密钥都产生独立的明文-密文关系

d.在所有2^k次（例如AES算法2^128）种可能性中搜索

e. T(k)=2T(k-1)

d.指数级算法（exponential algorithm）

密钥的大小

特点：

（1）密钥空间中的每个密钥都是可能的，而且先验的可能性相同

（2）暴力破解（brute force）最多需要2^k个步骤

（3）我们选择密钥的长度位数k，使其远远超过今天计算机所能达到的水平（但不要太多，为什么？）， AES算法中k为128位。

c.二次加密

定义：通过不同的密钥加密一个信息两次

攻击方法：

（1）中途相遇攻击（英语：Meet-in-the-middle attack）是密码学上以空间换时间的一种攻击。

方法：

当攻击者已知明文P与密文C时，攻击者可以穷举所有$k_{1}$的组合，将产生出来的第一层密文$\text{EN}C_{k_{1}}(P)$，用大量空间储存下来。再穷举所有$k_{2}$的组合，将$\text{DE}C_{k_{2}}(C)$的值与前面储存下来的结果比对，进而得出正确的$k_{1}$，$k_{2}$。

假设ENC是加密函式，DEC是解密函式，也就是$E N C^{-1}$，而k1与k2为两次加密用的秘钥，则可以推导出：

$$\begin{matrix} C = ENC_{k_{2}}(ENC_{k_{1}}(P)) \\ P = DEC_{k_{1}}(DEC_{k_{2}}(C)) \\ \Rightarrow ENC_{k_{1}}(P) = DEC_{k_{2}}(C) \\ \end{matrix}$$

d.幂模（modular Exponentiation）

定义：

模幂运算是整数 b（底数）的幂 e（指数）除以正整数 N（模数）的余数；

c = b ^e mod N

举例：4^3(64)=4（mod15）

（1）当幂太大时：

1.平方和乘法（Solution: Square-and-Multiply）

https://zh.wikipedia.org/wiki/平方求幂

**定义：**不断用平方和去逼近，缩小单次的幂指数

$$x^{15} = {x(x{(x*x^{2})}^{2})}^{2}$$

2.加法链求幂

https://en.wikipedia.org/wiki/Addition-chain_exponentiation

**二进制，**6次乘法：即平方和乘法

**最短加法链，**5次：

$$x^{15} = {x^{3}({(x^{3})}^{2})}^{2}$$