一、算法基础

1.循环不变量的证明

  • 初始化：证明循环不变量在循环开始前为真；
  • 保持：证明每次循环之后循环不变式仍为真；
  • 终止：循环可以有限次终止。

2.时间复杂度的分析

  • 整个算法的执行时间是执行所有语句的时间之和；
  • 算法的执行时间可能依赖于给定的输入，即使规模相同
  • 分析执行时间时可以分析算法的最坏执行情况、最好执行情况、平均执行情况。

3.算法的五个特性

  • 确定性

  • 能行性

  • 输入

  • 输出

  • 有穷性

    仅仅不满足有穷性规则的算法称为计算过程，如操作系统

二、算法渐近

1.限界函数

(1)上界函数

上界函数描述了算法最坏情况下的时间复杂度，记为$f(n)\inΟ(g(n))$或$f(n)=Ο(g(n))$

(2)下界函数

下界函数描述了渐进下界，记为$f(n)\in\Omega(g(n))$或$f(n)=\Omega(g(n))$

(3)渐近紧确界函数

渐近紧确界函数代表算法在最好和最坏情况下的计算时间就一个常数因子范围内而相同，既有$f(n) = \Omega(g(n))$，又有$f(n) = Ο(g(n))$

(4)记号说明

  • 这里的”$=$”不是通常相等的含义，代表属于
  • $\Theta(1)$表示具有常量计算时间的复杂度，即算法的执行时间为一个固定量，与问题的规模$n$无关

(5)非渐近紧确的上下界

  • $o$记号

对任意正常数$c$，存在常数$n_0\gt 0$，使对所有的$n\geq n_0$，有$\vert f(n)\vert\leq c\vert g(n)\vert$，则记作：$f(n)=o(g(n))$

  • $\omega$记号

对任意正常数$c$，存在常数$n_0\gt0$，使对所有的$n\geq n_0$，有$\vert f(n)\vert\geq c\vert g(n)\vert$，则记作：$f(n)=\omega(g(n))$

2.估算复杂性定理

  • 多项式定理：关于$n$的$m$次多项式与最高阶$n^m$同阶
  • $n^x(\log n)^y<n^{x+\varepsilon}$
  • $(\log n)^x<n$
  • $n^x<2^n$

3.上界函数定理

  • 正线性性：$d(n)=O(f(n))$，则$ad(n)=O(f(n))$，其中$a>0$
  • 加法律：$d(n)=O(f(n))$，$e(n)=O(g(n))$，则$d(n)+e(n)=O(f(n)+g(n))$
  • 乘法律：$d(n)=O(f(n))$，$e(n)=O(g(n))$，则$d(n)e(n)=O(f(n)g(n))$
  • 指数性质：$n^x=O(a^n)$，其中$x>0$，$a>1$
  • 对数性质1：$\log n^x=O(\log n)$，其中$x>0$
  • 对数性质2：$(\log n)^x=O(n^y)$，其中$x>0$，$y>0$

三、分治思想

1.分治原理

分治原理的基本思想：当问题规模比较大而无法直接求解时，将原始问题分解为几个规模较小、但类似于原始问题的子问题，然后递归地求解这些子问题，最后合并子问题的解以得到原始问题的解。

2.递归式求解

(1)基本形式

  • 求解递归式的目的是将递归式转换为渐近限界函数表示‌；

  • 一般关系为$T(n) =T(n_1)+T(n_2)+f(n)$，其中$f(n)$表示除递归以外的代价。

(2)预处理

  • 减去一个低阶项以便于代换法中的归纳证明，如$cn-d$

    减去低阶项往往能够使数学证明顺利进行：

  • 对取整符号进行简化

    如$T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+f(n)$，往往忽略上下取整函数，写作以下简单形式：$T(n)=2T(n/2)+f(n)$

  • 对对数或指数做代数转换

    改变变量来简化递归式：

  • 对限界函数项进行展开，便于化简

    对于$T(n)=3T(\lfloor n/4\rfloor)+\Theta(n^2)$，简化为$T(n)=3T(n/4)+cn^2$。

(3)求解方法

①代入法

  • 利用熟悉或类似的递归式猜测解的形式

  • 用数学归纳法证明猜测的正确性，得出合适的$c$值以满足条件

  • 讨论边界条件的正确性

    代入法实例如下：

②递归树

  • 在内部节点中表达除递归以外的代价

    对于$T(n)=aT(n/b)+f(n)$，一般假设$n=b^k$，$k=\log_bn$简化计算

  • 列出递归树直至叶子节点，得到递归树高度

    递归至叶子节点后，递归树的层数一般为$\log_bn+1$

    举例如下：

  • 计算内部某层节点的总代价、叶子节点总代价、树的总代价

    通过计算前几层节点的总代价，得到内部某层节点的总代价的通式；

    计算叶子节点的数目，假设为$num$，则叶子节点的总代价为$\Theta(num)$；

    根据等比数列求和公式得到总代价。

    计算如下：

  • 根据树的总代价猜测渐近限界函数

    猜测如下：

  • 利用代换法证明猜测

    证明如下：

③主方法

设$a≥1$，$b>1$，设$f(n)$为渐近正的函数，$T(n)$是定义在非负整数上的递归式：$T(n)=aT(n/b)+f(n)$，其中$n/b$指$\lfloor n/b \rfloor$或$\lceil n/b \rceil$，则可使用以下定理求解递归式：

  • 若对于某常数$\varepsilon>0$，有$f(n)=O(n^{\log_ba-\varepsilon})$，则$T(n)=\Theta(n^{\log_ba})$

    该情况中$n^{\log_ba}$比较大，$f(n)$需多项式地小于$n^{\log_ba}$，即对某个常量$\varepsilon>0$，$f(n)$必须渐近地小于$n^{\log_ba}$，两者相差了一个$n^\varepsilon$因子，如$T(n)=2T(n/2)+n\log n$和$T(n)=4T(n/2)+n^2\log n$不满足条件

  • 若$f(n)=\Theta(n^{\log_ba})$，则$T(n)=\Theta(n^{\log_ba}\log n)$

    该情况中两个函数一样大，乘以对数因子$\log n$

  • 若对于某常数$\varepsilon>0$，有$f(n)=\Omega(n^{\log_ba+\varepsilon})$，且对常数$c<1$与足够大的$n$，有$af(n/b)\leq cf(n)$，则$T(n)=\Theta(f(n))$

    该情况中$f(n)$比较大，$f(n)$需多项式地大于$n^{\log_ba}$，并需要满足一个规则性条件$af(n/b)\leq cf(n)$，注意其中$c< 1$

3.归并排序

(1)问题描述

已知包含$n$个数字的序列$A[1,\dots,n]$，对其进行升序排序。

(2)问题分析

  • 将数组$A$排序问题分解为$A[1,\dots,\lfloor\frac{n}{2}\rfloor]$和$A[\lfloor\frac{n}{2}\rfloor+1,\dots,n]$排序问题；
  • 递归解决子问题得到两个有序的子数组；
  • 然后再将两个子数组合并，合并的代价即为除递归以外的代价；
  • 当数组被分解为长度为1时天然有序，从而产生局部有序性，进而进行两两合并操作。

(3)分治策略

  • 算法伪代码：

    $MERGE-SORT(A,left,right)$

    $MERGE(A,left,mid,right)$

  • 时间复杂度

    • 递归式为$T(n)=2T(n/2)+O(n)$，其中$O(n)$为$MERGE$操作的时间代价；
    • 时间复杂度为$O(n\log n)$。

4.最大子数组问题

(1)问题描述

  • 寻找和最大的非空连续子数组
  • 给定一个数组$X[1..n]$，对于任意一对数组下标为$l,r(l\leq r)$的非空子数组，其和记为$S(l,r)=\sum\limits_{i=l}^{r}{X[i]}$，求$S(l,r)$的最大值，记为$S_{max}$。

(2)暴力求解

  • 枚举$n+C_n^2$种下标$l,r$组合，求出最大子数组之和；
  • 处理每对下标组合最少的时间代价为常量；
  • 时间复杂度为$\Omega(n^2)$。

(3)分治策略

  • 将子数组$A[low…high]$划分为两个规模尽量相等的子子数组；

  • 分别求解$A[low…mid]$和$A[mid+1…high]$的最大子数组；

  • 基于上述划分，存在三种连续子数组情况：$mid$左侧、跨越$mid$、$mid$右侧；

  • 对于跨越$mid$的情况，从$mid$出发，分别向左和向右找出最大子区间并合并，这个步骤的代价即为除递归以外的代价，其时间复杂度为$\Theta(n^2)$；

    算法$FIND-MAX-CROSSING-SUBARRAY$如下：

  • 对于其他两种情况，递归调用FIND-MAXIMUM-SUBARRAY即可；

  • 求最大子数组问题的分治算法

    FIND-MAXIMUM-SUBARRAY如下图：

  • 时间复杂度

    • 当$n=1$时，$T(n)=\Theta(1)$；
    • 当$n>1$时，$T(n)=2T(n/2)+\Theta(n)$；
    • 时间复杂度为$T(n)=\Theta(n\lg n)$。

※(4)非递归的线性算法

※5.$Strassen$矩阵乘法

6.最近点对问题

(1)问题描述

  • 已知平面上分布着点集$P$中的$n$个点$p_1,p_2,\dots,p_n$，点$i$的坐标记为$(x_i,y_i)$，$1\leq i\leq n$。
  • 找出一对距离最近的点(允许两个点处于同一个位置)

(2)暴力搜索

  • 对每对点都计算距离，然后比较大小，找出其中的最小者
  • 计算点之间的距离的时间复杂度为$O(n^2)$
  • 比较得到最小距离的时间复杂度为$O(n^2)$

(3)分治策略

  • 排序：将所有点按照$x$坐标排序——$O(n\log n)$

  • 划分：将点集分成左、右两半$P_L$和$P_R$

    定义$d_L$为$P_L$中最近点对距离，$d_R$为$P_R$中最近点对距离，$d_C$为跨越分割线的最近点对距离，这与最大子数组问题类似。

  • 改进：令$\delta=min(d_L,d_R)$，则有$d_C<\delta$，即$d_C$对应点对必然落在分割线两侧的$\delta$距离内，称之为$strip$，同时易得，$d_C$的两个点的$y$坐标相差也不会大于$\delta$，因此应该对点的$y$坐标也进行排序。

  • 实现：假设搜索到$p_j$时，$p_j$与$p_i$的$y$坐标相差大于$\delta$，那么对于$p_i$而言更远的$p_j$就可以终止搜索，转而处理$p_i$后面的点$p_{i+1}$。

    改进后的算法伪代码：

    1
    2
    3
    4
    5
    6
    for i=1 to numPointsInStrip do
    	for j=i+1 to numPointsInStrip do
    		if y-coordinates of p[i] and p[j] differ by more than δ
    			break;
    		else if dist(p[i],p[j])<δ
                δ=dist(p[i],p[j]);

  • 时间复杂度

    • 在最坏的情况下，计算$d_C$的时间复杂度为$O(n)$，则最终递归式为$T(n)=2T(n/2)+O(n)$
    • ※预排序
    • 综上得到所有附加工作的总时间复杂度为$O(n)$，则$T(n)=2T(n/2)+cn=O(n\log n)$

7.逆序对计数问题

(1)问题描述

  • 在一个数组$A$中，称满足$i<j$且$A[i]>A[j]$的二元组$(A[i],A[j])$为逆序对

    在数组$A={4,6,8,3,5}$中，$(A[1],A[4])$即为一个逆序对

  • 现已知长度为$n$的数组$A[1..n]$，求其逆序对的总数$\sum\limits_{1\leq i\leq j\leq n}X_{i,j}$，其中当$A[i]>A[j]$时$X_{i,j}$为1，否则为0。

(2)暴力枚举

  • 对于每个元素$A[i]$，枚举$j(j>i)$，并统计逆序对数目；
  • 时间复杂度为$O(n^2)$。

(3)分治策略

  • 将子数组$A[low\dots high]$划分为两个规模尽量相等的子子数组；

  • 分别递归求解仅在$A[low\dots mid]$和$A[mid+1\dots high]$中的逆序对数目；

  • 合并子问题的解时，求解跨越子数组的逆序对数目；

  • 求解跨越子数组的逆序对数目

    • 直接求解：对于每个$A[j]\in A[mid+1\dots high]$，枚举$A[i]\in A[low\dots mid]$并统计逆序对数目——算法运行时间为$O(n^2)$，得到分治策略运行时间为$O(n^2)$；

      运行时间受制于跨越子数组的逆序对计数方法，数组的有序性通常有助于提高算法的运行时间。

    • 排序求解：分别对数组$A[low\dots mid]$和$A[mid+1\dots high]$进行排序，对于每个$A[j]\in A[mid+1\dots high]$，采用二分查找为其在$A[low\dots mid]$中定位，则$A[j]$在$A[low\dots mid]$定位点右侧的元素均可与$A[j]$构成逆序对——算法运行时间为$O(n\log n)$，得到分治策略运行时间为$O(n(\log n)^2)$；

      排序和二分查找均无再优化空间，但未将排序过程融入整个算法框架；

      排序未利用子数组有序性质——使用归并排序；

      合并问题解的同时对数组进行排序，归并过程中可同时计算逆序对数目。

    • 归并求解：从左到右扫描$A[low\dots mid]$和$A[mid+1\dots high]$，如果$A[i]>A[j]$，统计逆序对，$j$向右移；否则$i$向右移——算法运行时间为$O(n)$，得到分治策略运行时间为$O(n\log n)$。

  • 分而治之+归并求解

    MergeCount：

    CountInver：

  • 时间复杂度

    • 归并求解的算法运行时间为$o(n)$；
    • $T(n)=2T(n/2)+O(n)$；
    • 时间复杂度为$T(n)=O(n\lg n)$。

8.快速排序

(1)问题描述

  • 选择排序和插入排序的时间复杂度均为$O(n^2)$；
  • 归并排序简化分解，侧重合并，快速排序侧重分解，简化合并。

(2)分治策略

  • 选取固定位置主元$x$，如尾元素；

  • 维护两个部分的右端点下标变量$x,y$；

  • 考察数组元素$A[j]$，并只和主元比较：若$A[j]\leq x$，则交换$A[j]$和$A[i+1]$，$i$和$j$右移，否则$j$右移；

  • 到达末尾后，把主元放在中间$(i+1)$处作为分界线；

  • 以主元作为数组的划分，得到子数组分别进行PARTITION排序，排序后进行合并

  • 伪代码如下：

    Partition：对每个子数组进行排序操作，返回主元位置$p$

    QuickSort：利用Partition和分治策略进行快速排序

  • 时间复杂度

    • 选取固定位置主元时最好情况下为$O(n\log n)$，最坏情况下为$O(n^2)$

    • 选取随机位置主元，可以避免最坏情况的发生

      Randomized-Partition：

      Randomized-QuickSort：

    • 随机化的快速排序的期望复杂度为$O(n\log n)$

    • 基于比较的排序，其时间复杂度的下界为$\Omega(n\log n)$。

9.次序选择问题

(1)基本概念

  • 顺序统计量：在一个由$n$个元素组成的集合中，第$i$个顺序统计量$(order statistic)$是该集合中的第$i$小的元素

  • 中位数（一般指下中位数）

    • 下中位数：$i=n/2$或$i=\lfloor(n+1)/2\rfloor$
    • 上中位数：$i=n/2+1$或$i=\lceil(n+1)/2\rceil$

  • 选择问题：从$n$个元素的集合中选择第$i$个顺序统计量的问题形式化地归结为“选择问题”

    • 输入：一个包含$n$个（互异的）数的集合$A$和一个整数$i$，$1\leq i\leq n$
    • 输出：元素$x\in A$,且$A$中恰好有$i-1$个其他元素小于它

  • 采用排序求解的方式解决选择问题时，其时间复杂度为$O(n\log n)$，可以求得所有元素的次序，选择元素的时间复杂度为$O(1)$。

(2)期望为线性时间的选择算法

  • 受启发于快速排序的Partition过程：

  • 选择算法：

    第1行检查$A[p..r]$中只包括一个元素的情况；

    其余情况调用第3行的RANDOMIZED-PARTITION，将数组$A[p..r]$划分为两个子数组$A[p..q-1]$和$A[q+1..r]$（可能为空），使前者的每个元素都小于$A[q]$，后者的每个元素都大于$A[q]$，称$A[q]$为主元；

    第4行计算处于划分的低区的元素个数加1；

    第5行检查$A[q]$是否为第$i$小的元素；

    如果不是，则确定第$i$小的元素是在哪个子数组并在其中递归查找，当$i>k$时，要找的元素必定为$A[q+1..r]$中第$i-k$小的元素。

  • 最坏情况运行时间为$\Theta(n^2)$，期望运行时间为$\Theta(n)$

※(3)最坏情况为线性时间的选择算法