算法期中复习

lecture1

整数乘法

正常竖式乘法的复杂度是

分治：

两个位数乘法分治成四个位数乘法，复杂度仍是，每次分治还有三次加法

Multiply(x,y,n):
  if n==1:
    return x*y
    
  a = x/pow(10,n/2)
  b = x%pow(10,n/2)
  c = y/pow(10,n/2)
  d = y%pow(10,n/2)
  
  ac = Multiply(a,c,n/2)
  ad = Multiply(a,d,n/2)
  cb = Multiply(c,b,n/2)
  bd = Multiply(b,d,n/2)
  
  xy = ac*pow(10,n)+(ad+cb)*pow(10,n/2)+bd
  return xy

Karatsuba乘法

两个位数乘法分治成三个位数乘法，复杂度变为，有所改善

Multiply(x,y,n):
  if n==1:
    return x*y
    
  a = x/pow(10,n/2)
  b = x%pow(10,n/2)
  c = y/pow(10,n/2)
  d = y%pow(10,n/2)

  ac = Multiply(a,c,n/2)
  bd = Multiply(b,d,n/2)
  z = Multiply(a+b,c+d,n/2)

  xy = ac*pow(10,n)+(z-ac-bd)*pow(10,n/2)+b
  return xy

将位数乘法分治成五个位数乘法，复杂度

经过学者不断改进，达到了

推广

• 两个乘数长度不同：在短的那个数的前⾯补0
• n不是偶数：前⼀半n/2向下取整，后⼀半n/2向上取整
• 计算与相乘：后面补n个0

InsertionSort算法

def InsertionSort(A):
    for i in range(1,len(A)):
        current = A[i]
        j = i-1
        while j >= 0 and A[j] > current:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = current

算法复杂度渐进性分析

表示上界

等价于

存在，使得任意，都有

表示下界

等价于

存在，使得任意，都有

表示上界和下界

等价于

且

证明方法

• 证明：提出和满足定义

证明:

令

则对于任意，

• 证明不是，反证法：假设存在一个和一个满足定义，通过推导出一个矛盾来证明

证明:对任意，不是

假设是，则存在，使得对任意，都有

则对任意，都有，当时显然不成立，产生矛盾。

• 对于，既没有，也没有。

只要保证随着的增大，和之间的关系忽大忽小即可。

算法分析的三个指导原则

1. 最坏情况分析
2. 忽略常数因子和低阶项
3. 渐进分析

lecture2

Mergesort归并排序

MergeSort(A):
    n = length(A)
    if(n <= 1)
        return A
    L = MergeSort(A[0:n/2])
    R = MergeSort(A[n/2:n])
    return Merge(L,R)

Merge(L,R):
    n = length(L) + length(R)
    A[n], i = 0, j = 0
    for k in range(0,n):
        if L[i] < R[j]:
            A[k] = L[i], i = i + 1  
        else:
            A[k] = R[j], j = j + 1     
    return A

复杂度证明

每层步，一共层

渐进地比InsertionSort的好

逆序对数

站在MergeSort的肩膀上，在MergeSort的Merge过程中，同时进行排序和数逆序对。

对左右两个已经排序的数组进行Merge时，右侧每个数字被放入合并数组时，左侧剩余的数字个数，即是与此数字构成的分离逆序对数量。

，复杂度

主定理

证明

替换法

• 对正确答案进行猜测
• 试着证明你的猜测是正确的
  • 若的表达式中无，直接对表达式进行归纳假设
  • 若的表达式中有，利用进行归纳假设，找到适合的常数，替换不等式中的后，再进行正式证明
• 得到复杂性结果

lecture3

替换法可能遇到的问题

• 找不到合适的，可能是前面的假设错误了
• 若的递归表达式中含有常数，如，则可以调整假设的不等式为，解决常数部分带来的影响

当主定理不起作用时，替换法可以起作用

k-select

Select(A,k):
    If len(A) <= 50:
        A = MergeSort(A)
        Return A[k-1] 
    p = getPivot(A) // return some pivot 
    L, pivotVal, R = Partition(A,p) // split up A to L,A[p],R
    if len(L) == k-1:
        return pivotVal
    else if len(L) > k-1:
        return Select(L, k)
    else if len(L) < k-1:
        return Select(R, k – len(L) – 1)

运行时间受pivot位置的影响

理想的pivot

• 基于MergeSort：选取最中间的数当pivot(假设可以选出)，由主定理可证明，时间复杂度为
• RSelect：在A中均匀随机地选取pivot
  • 最坏情况下时间复杂度为
  • 虽然最坏情况下时间复杂度为，但平均性能比基于MergeSort的方法还好
• DSelect：选取中位数当pivot
  • 只要这个pivot不要太偏两边即可：，
  • 分成组，每组5个。先在每组中寻找中位数，再在这个中位数中寻找中位数。最终这个中位数即为pivot。

替换法证明渐进复杂度

猜测

假设,有

化简得,.令即可得证

怎么来的

• :子数组个数（5个数一组）
• :大于pivot的数的最大个数

对于m个数一组

例如:

• 时，
• 时，
• 时，

lecture4

BogoSort

BogoSort(A):
    while true:
        随机排列A
        if(A is sorted)
            return A

期望时间

$$
E[在长度为n的列表上的运行时间]=E[(迭代次数)(每次迭代时间)]=(每次迭代时间) E[迭代次数]=O(n⋅n!)
$$

最坏运行时间：INF

关于随机算法

• 期望运行时间：

  • 公布随机算法
  • 对抗性输入
  • 自己的随机策略

• 最坏运行时间：

  • 公布随机算法
  • 对抗性输入
  • 对抗性随机策略

QuickSort

期望运行时间，最坏运行时间

QuickSort(A):
    if len(A) <= 1:
        return
    随机选择pivot
    将A的其余部分分成:
        L (小于pivot)
        R (大于pivot)
    重新排列A为[L, x, R]
    QuickSort(L)
    QuickSort(R)

• 选定最中间的数当pivot，即，得出

• 证明随机的期望运行时间为
  
  
  即选定最中间的数当pivot的情况

QuickSort vs MergeSort

• QuickSort(随机pivot)：期望，最坏

• MergeSort(选定pivot)：最坏

比较类排序算法复杂度下界

任何比较类排序算法都至少需要；其他类的可以达到，如计数排序、基数排序

用决策树证明比较类排序算法的下界

• 最好运行时间：至少是从根结点到相应叶结点的路径长度，即决策树的深度

• 最差运行时间：至少是树中最长路径的长度。最长路径至少为，约为

lecture5

摊还分析

• 聚合分析：计算之后除以，计算平均值
• 记账方法：对廉价的业务征收额外费用，并在以后用于支付昂贵的业务，构造实际费用的上界
• 势方法：给出一个势函数，表征在每一步中可以做的额外工作量，构造实际成本的一个上界

小结

• 主定理：等分的分治递归算法
• 替换法：非等分的分治递归算法
• Worst Case分析：给出worst case的递推表达式（D-Select）
• 期望运行时间分析：用统计分析的方法求各期望运行场景，统计期望运行时间（QuickSort）
• 摊还分析：分析n个连续操作的worst case运行时间，摊算到每个操作上，主要有聚集法，记账法，势能法（栈、二进制计数器、动态表、Hash表、Spray Tree等）

二叉搜索树

search、insert、delete都是，在平衡的二叉搜索树中为

后继

• 如果右孩子非空，转向右孩子后，不断找左孩子直到叶节点。
• 如果右孩子为空，则一直向上找，直到当前节点是它父亲的左孩子。

前驱

• 如果左孩子非空，转向左孩子后，不断找右孩子直到叶节点。
• 如果左孩子为空，则一直向上找，直到当前节点是它父亲的右孩子。

AVL树

balance(v)=height(v.right)-height(v.left),balance(v)∈{-1,0-1}

Rotation

BSTNode rotateRight(BSTNode p) { // 往右转
    BSTNode q = p.left;
    p.left = q.right;
    q.right = p;
    return q;
}
BSTNode rotateLeft(BSTNode p) { // 往左转
    BSTNode q = p.right;
    p.right = q.left;
    q.left = p;
    return q;
}

组合旋转

rotateLeftRight(p)：先往左转，再往右转

rotateRightLeft(p)：先往右转，再往左传

懒惰删除

由于删除的操作比较复杂，在实际实现的时候，考虑经常是插入较多，删除较少，所以为树中每个节点设置一个alive, dead的标签。

2-3树

部分节点有两个孩子，部分节点可以有三个孩子

插入

• 如果它是2-node，插入之后变为3-node，没问题。

• 如果它是3-node，插入后，临时变为4-node，再拆成两个节点，将中间的数提升一层。

删除

删除后用后继节点替换，再修复维护树的结构（不断merge，最后再adopt）

红黑树

插入、删除、查找都是

属性

• 每个结点不是红就是黑

• 根结点是黑

• 每个叶结点(NIL)为黑色

• 如果一个节点是红色的，那么它的两个子节点都是黑色的，即从根到叶的一条简单路径上没有两个连续的红色节点

• 对于每个节点，从该节点到叶节点的所有路径包含相同数量的黑节点，即黑高度相同。

  • 黑高度bh(x):从x到叶子的路径上的黑节点数(包括NIL)，不包括x。

树高

有个内部节点的红黑树高度不超过

插入

插入节点颜色默认为红色，若父亲也为红色则需要调整：

• z的叔叔为红色

  • z的祖父必为黑色
  • 将z的父亲、叔叔改为黑色；祖父改为红色
  • 红色会向上传播，所以要继续向上修改

• z的叔叔是黑色，且z是左孩子

  • 将z的父亲改为黑色；祖父改为红色；
  • 右旋祖父节点

• z的叔叔是黑色，且z是右孩子

  • 右旋父节点，然后z就变成了左孩子，与上条情况相同

• 如果红色传播到了根节点，强制将根节点染黑即可

删除

类似，重新上色、旋转

lecture6

Range Tree

1D Range Search

void rsearch(TreeNode root, int l, int r) {
    if (root == null) {
        return;
    }
    if (root.val > l) {
        rsearch(root.left, l, r);
    }
    if (root.val >= l && root.val <= r) {
        results.add(root.val);
    }
    if (root.val < r) {
        rsearch(root.right, l, r);
    }

2D Range Tree

BuildTree(S):
    if |S|==1:
        return 叶节点t
    选出按X排序的中位数x
    小于x的部分为L,大于x的部分为R
    t.val = x
    t.left = BuildTree(L)
    t.right = BuildTree(R)
    t.ytree = MergeYTree(t.left.ytree,t.right.ytree)
    return 节点t

空间，建树时间

2D搜索：先1D搜索x。如果x满足区间，则在对应的ytree里1D搜索y；否则继续1D搜索x。

KD：搜索时间，空间

K-D Tree

一层按x分割，一层按y分割，均选取中位数作为分割点

insert

直接插入至叶节点即可

delete

• 如果当前节点包含待删除的点

  • 如果是叶节点，直接删除即可
  • 如果不是叶节点
    • 如果有右孩子，则在右侧子树中查找当前节点维度的最小值。用找到的最小值替换节点。
    • 如果没有右孩子，则在左侧子树中查找当前节点维度的最小值。用找到的最小值替换节点，并递归地删除左子树中的最小值。将新的左子树作为当前节点的右子树。

• 如果当前节点不是要删除的点

  • 如果要删除的节点在当前维度上小于当前节点，则递归左子树。
  • 否则递归右子树。

search

Query(t,r):  // r:query range
    if t是叶节点:
        return t
    if t.range 包含在r内:
        子树中的点全部加入答案
    else if t.range 与r相交:
        Query(t.left,r)
        Query(t.right,r)

查询时间

总结

d维	KD Tree	Range Tree
排序
空间
查询时间

lecture7

Quad Tree

• 每个内部节点最多有四个子节点。

• 四叉树中的每个节点都对应一个正方形。

• 节点v的子节点对应于正方形v的四个象限。

• 节点的子节点被标记为NE, NW, SW和SE，以指示它们对应于哪个象限。

最近邻搜索 in Quad Tree

• 初始化一个大圆r

• 将根节点压入栈中

• 不断重复：

  • 从栈中pop出来T

  • 对于T的每一个孩子C：

    如果C与r相交，就把C压栈

    如果C是叶子，检验C中的点，更新r

• 问题：

  • 四叉树可能有很多空的节点
  • 如果点比较稀疏，那么需要很长的时间才能找到最近邻

最近邻搜索 in K-D Tree

• 遍历整棵树

• 保留一个目前为止找到最近的点C。当子树的边界框不包含任何距离C更近的点时，剪枝。

• 从包含Q的子树开始回溯，然后递归地检查可能包含更接近Q的点的子树。

在大多数情况下，运行时间更接近于

其中为访问在查询点附近的一些节点集，为查找这些节点

k近邻搜索KNN

• 通过保持个当前最佳值来找到一个查询的个最近邻居。

• 分支只有在不能有比个当前最佳值更近的点时才会被剪枝。

• 复杂度为，当d较大时不适合。当d是一个常数时，它是

• 区域查询的复杂度为

PCP Tree

• 分裂的方向可以不是x和y。

• 将垂直于最宽分布轴的点分开。

• 主成分划分（PCP）

近似最近邻ANN

• 仅检查K-D Tree中最接近的N个bin
• 使用优先级队列按其与查询的距离顺序排列bin
• 返回高概率的最近邻居(例如95%)

Best Bin First(BBF)：查询点首先查找包含它的Bin，然后查找相邻的Bin，而不是在树中最近的邻居。会快很多

ε-ANN

查找具有高概率的最近邻，即查找P中的点p’，其到q的距离至多是真实最近距离R的(1+ε)倍。使得高维空间的查找更高效。

局部敏感哈希

构造了一组位置敏感的哈希函数，使得在哈希函数转换后，附近点接近的概率大于两个遥远点在同一转换后接近的概率。

降维

• 想法：找到一个映射T来降低数据的维数

• 缺点：可能无法找到所有相似的对象(即，距离关系可能无法保存)

K-D Tree总结

• 使用条件：适用于低维海量数据点

  • ，二维坐标、三维坐标的云处理

• d较大时需要近似最近邻，找到k个最近的

lecture8

层次聚类树

空间：

建树：

k-NN：

Hash

• 可以再先mod q，再mod m，会更加随机
  • 除法散列：
  • 乘法散列：
  • 线性散列：
• 多项式哈希
• 随机化和通用的哈希：如果哈希函数是从一大类函数中随机选择的，并且任意两个固定键之间碰撞的概率为，则哈希方案被称为通用。

分离链接法

装填因子：

如果条目是均匀分布的：

• 成功搜索：平均搜索一半的列表，
• 失败搜索：要搜索整个列表，

重哈希：如果装填薪因子或者，则重新构建哈希表和哈希函数，令，，平摊复杂度

开放寻址法

• 线性探测：

  • 就表现得很好，但容易受到二次聚类的影响，需要经常重哈希
  • 搜索成功：
  • 搜索失败：

• 平方探测：

  • 可能无法命中所有单元
  • 如果表大小是一个素数，前个探测序列是不会发生冲突的

• 双重哈希：

  • 探测时定位使用
  • 冲突时偏移量使用
  • 搜索成功：
  • 搜索失败：

布隆过滤器

空间和假阳性概率之间的权衡

假阳性概率:

局部敏感哈希(LSH)

尝试将相似的对象映射到相同的哈希bin，并将不相似的对象映射到不同的bin

哈希族ℋ是-对距离敏感：

• 若，则
• 若，则

LSH based ANN：看不懂