算法设计与分析 课程笔记

导引

算法是解决一确定类问题的任意一种特殊的方法：

• 数值计算方法：求解数值问题，如插值计算、数值积分等。

• 非数值计算方法：求解非数值问题，主要进行判断比较。

算法的非形式描述：算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。

五个重要特性

• 确定性：每一种运算必须要有确切定义，无二义性。

  • 反例：$5/0$, $1或2+x$

• 能行性：运算都是基本运算，原理上能用纸和笔在有限时间完成。

• 输入：有0个或多个输入。在算法开始之前，从特定的对象集合中取值。

• 输出：一个或多个输出。这些输出和输入有特定关系。

• 有穷性：在执行了有穷步运算后终止。

  • 要在现代计算机上有效

  • 计算过程可以不满足有穷性

例如操作系统，当没有任务时，操作系统并不终止，而是处于等待状态，直到有新的任务启动，因而不是一个算法。

算法学习的内容

算法设计

面对具体问题，运用一些基本设计策略，规划算法。

算法表示

采用SPARKS程序设计语言。

算法确认

证明该算法对所有可能的合法输入，都能给出正确答案。

• 穷举法

• 数学归纳法、反证法

• 构造性证明

• 测试

算法分析

在最好、最坏、平均情况下分析时间、空间复杂度。

算法分析

时间的渐进表示

$O$ 符号

如果存在两个正常数 $c$ 和 $n_0$，对于所有的 $n \ge n_0$ ，有 $|f(n)|\le c|g(n)|$ ，则记作： $f(n)=O(g(n))$ 。

• 当$n$充分大时，$f(n)$有上界，一个常数倍的$g(n)$是$f(n)$的一个上界，$f(n)$的数量级就是$g(n)$。

• $f(n)$的阶不高于$g(n)$的阶。

• 在确定$f(n)$的数量级时，总是试图求出最小的$g(n)$。

• 有关证明中，找出$c$和$n_0$是关键。

主要性质：

1. $O(f(n))+O(g(n))=O(max(f(n),g(n))$

不妨设$p(n)= \max{f(n),g(n)}$

设$f’(n)=O(f(n))$，则存在$c_1,n_1$，当$n≥n1$时， $f’(n) ≤c_1*f(n)$

设g’(n)=O(g(n))，则存在c2,n2，当n≥n2时， g’(n) ≤c2*g(n)

则O(f(n))+O(g(n)) =f’(n)+g’(n)

当n ≥max{n1,n2}时，

f’(n)+g’(n) ≤c1f(n)+ c2g(n) ≤c1p(n)+ c2p(n)=(c1+c2)*p(n)

即存在c3=c1+c2，n3= max{n1,n2}，当n ≥n3时，f’(n)+g’(n) ≤c3*p(n)

故O(f(n))+O(g(n)) = O(max{f(n),g(n)})

2. $O(f(n))+O(g(n))=O(f(n)+g(n))$

3. $O(f(n))O(g(n))=O(f(n)g(n))$

4. $g(n)=O(f(n))\Longrightarrow O(f(n))+O(g(n))=O(f(n))$

5. $O(cf(n))=O(f(n)),c>0$

6. $f(n)=O(f(n))$

7. 若$A(n)=a_mn^m+…+a_1n+a_0$是一个$m$次多项式，则$A(n)=O(n^m)$

证明：取n0=1，当n≥n0时

​ 由A(n)的定义和不等式关系|A+B| ≤ |A|+|B|有

|A(n)| = |amnm+…+a1 n+a0 | ≤ |am|nm+…+|a1 | n+|a0 |

​ = (|am|+|am-1|/n …+|a0 |/nm ) nm

​ ≤ (|am|+|am-1|…+|a0 |) nm

取 c= |am|+|am-1|…+|a0 |，有|A(n)| ≤cnm

即：A(n)=O(nm)，定理得证。

$\Omega$ 符号

如果存在两个正常数$c$和$n_0$，对于所有的$n\ge n0$，有$|f(n)| \ge c|g(n)|$，则记作：$f(n)=\Omega(g(n))$。

1. W(f(n))+ W(g(n)) = W(min(f(n), g(n)) ;

2. W(f(n))+ W(g(n)) = W(f(n)+g(n)) ；

3. W(f(n)) W(g(n)) = W(f(n) g(n)) ；

4. 如果g(n) = W(f(n)) ，则W(f(n))+ W(g(n)) = W(f(n)) ；

5. W(cf(n)) = W(f(n)) ，其中c是一个正的常数；

6. f(n) = W(f(n))。

$\Theta$ 符号

如果存在正常数c1,c2和n0，对于所有的n≥n0，有c1|g(n)|≤ |f(n)| ≤ c2|g(n)|，则记作：f(n)= \Theta(g(n))。

若干性质

• 传递性

lf(n)= Q(g(n))， g(n)= Q(h(n)) Þ f(n)= Q(h(n))；

lf(n)= O(g(n))， g(n)= O (h(n)) Þ f(n)= O (h(n))；

lf(n)= W(g(n))， g(n)= W (h(n)) Þ f(n)= W(h(n))；

• 反身性

$f(n)= \Theta(f(n))$

$f(n)= O(f(n))$

$f(n)= \Omega(f(n))$

分治法

分治法适用于**$n$取值相当大**，直接求解往往非常困难，甚至无法求出；将$n$个输入分解成$k$个不同子集，得到$k$个不同的可独立求解的子问题；在求出子问题的解之后，能找到适当的方法把它们合并成整个问题的解的情况。

二分查找

procedure BINSRCH(A, n, x, j)
  integer  low, high, mid, j, n;
  low<-1;    high<-n
  while low≤high do 
           mid← ⌊(low+high)/2⌋      
           //取中间值
        case
           :x<A(mid):  high<-mid-1 //前一半
           :x>A(mid):  low<-mid+1  //后一半
           :else:   j<-mid;  return;    //查找成功结束
        endcase
    repeat  
  j<-0     //查找失败
end BINSRCH

算法正确性证明

• 如果n==0，则不进入循环，j=0，算法终止。

• 否则就会进入循环与数组A中的元素进行比较。

  • 成功情况：

    • 若x==A[mid]，则j=mid，查找成功，算法终止。

    • 否则，若x<A(mid)，则x根本不可能在mid ~ high,查找范围缩小到low ~ mid-1。反之，x>A(mid)时亦然。

  • 不成功情况：
    • 因为low，high和mid都是整形变量，按算法所述方式缩小查找范围总可以在有限步内使low>high，说明x不在A中，退出循环，j=0，算法终止。

  证明思路：

  1. 检验到参数的每类取值

  2. 检验到算法的每个分支

时间复杂度分析

$A$有$n$个元素，$x$和$A$中元素比较

• 成功查找：$n$种情况

• 不成功查找：$n+1$种情况

对于一棵$n$个元素的，内节点最大级数为$k$的二元比较树，其$k-1$层必为满。故$2k-1 \le n< 2k$，所以若$n$在区域$[2^{k-1}, 2^k)$中，则对于一次成功的查找，二分查找算法至多作$k$次比较，而对于一次不成功的查找，作$k-1$次比较或者作$k$次比较。

设：

• 内部路径长度$I$：根到所有内节点的距离之和

• 外部路径长度$E$：根到所有外节点的距离之和

则：

• 容易证明$E=I+2n$

• 成功查找的平均比较次数$S(n)=(I/n)+1=\Theta(\log N)$

• 不成功查找的平均比较次数$U(n)=E/(n+1)=\Theta(\log N)$

时间复杂度	最好情况	最差情况	平均情况
成功查找	$\Theta(1)$	$\Theta(\log N)$	$\Theta(\log N)$
失败查找	$\Theta(\log N)$	$\Theta(\log N)$	$\Theta(\log N)$

空间复杂度

只用$n$个位置存放数组$A$，还有$low, high, mid, x, j$五个变量需要存储，共需空间 $n+5= \Theta(n)$。

归并排序

Procedure MERGESORT(low,high)
int  low, high, mid;
if  low<high
    then   mid= ⌊(low+high)/2⌋
               call  MERGESORT(low,mid)
               call  MERGESORT(mid+1,high)
               call  MERGE(low,mid,high)
endif
end  MERGESORT

时间复杂度

归并排序算法消耗的时间：

$$T(n)= \begin{cases} a&&n=1,a为常数\\ 2T(n/2)+cn&&n>1,c为常数 \end{cases} \\ \Rightarrow T(n)=O(n\log n)$$

任何以关键字比较为基础的排序算法，最坏情况下的时间下界都是$\Omega(n\log n)$，因此从数量级角度看, 归并算法是最坏情况下的最优算法。

证明

已知$n$个关键字有$n!$种排列。

观察二元比较树从根到外节点的每一条路径，分别与一种唯一的排列相对应。则比较树必定至少有$n!$个外节点。且最坏情况下比较次数等于树高$T(n)$。

则必有：$$2T(n)\ge n! \ge (\frac{n}{2})^{\frac{n}{2}} \Rightarrow T(n)=O(n\log n) $$

斯特拉森矩阵问题

矩阵$A_{n×n}$和$B_{n×n}$的乘积矩阵$C_{n×n}$中的元素$C[i,j]$定义为:

$$C[i][j]=\sum_{k=1}^{n}A[i][k]B[k][j]$$

$C$有$n^2$个元素，一个元素需要做$n$次乘法和$n-1$次加法，总时间复杂度为$O(n^3)$。

优化

如果是将矩阵直接切割成子矩阵，实际上是不能优化的，因为并没有减少子问题的实际数量。

斯特拉森在分治法的基础上，利用技巧减少了子问题的个数。它用7个乘法和10个加(减)法来算出7个$\frac{n}{2}*\frac{n}{2}$的中间矩阵，用8个加(减)法算出子问题的解$C[i][j]$，让时间复杂度从$T(n)=8T(\frac{n}{2})+cn^2$减少到了$T(n)=7T(\frac{n}{2})+cn^2$，时间复杂度$O(n^{\log 7})$。

二维极大点问题

在二维空间中，如果$x_1>x_2$，且$y_1>y_2$，那么称点$(x_1,y_1)$支配点$(x_2,y_2)$，如果一个点没有被其他点支配，则称其为极大点。

求极大点问题就是找出一个空间中的所有极大点。

如果直接比较每一对点，时间复杂度$O(n^2)$。递归优化：

• 分：设计中位线$l$，将整个点集分为两个子集$S_L$和$S_R$

• 治：分别找出$S_L$和$S_R$的极大点

• 合：基于支配规则合并$S_L$和$S_R$的极大点

• 中位线：

  • 垂直于$x$轴的中位线L

  • 对集合$S$中的所有点按$x$值排序后，寻找第$n/2$点位置

• 递归出口：

  • 如果集合$S$中只有一个点，那么该点为极大点

• 基于支配规则合并：

  • 对于$S_L$中的极大点$p$，如果$y_p$小于$S_R$中极大点的$y$值，则$p$被支配，舍弃掉，因为$S_L$中的点的$x$值总是小于$S_R$中的点的$x$值

使用排序优化后的解法时间复杂度 $O(n \log n)$。

主定理

设 $a \geq 1, b > 1$ 为常数，$f(n)$ 为函数，$T(n)$ 为非负整数，且满足：

$$T(n) = aT(n/b) + f(n)$$

其中 $a$ 表示子问题数量， $f(n)$ 表示处理子问题消耗的时间规模。则 $T(n)$ 有如下渐近界：

1. 若 $f(n)$ 的数量级低于 $O(n^{\log_b a})$ 则有：

   $$T(n) = \Theta(n^{\log_b a})$$

2. 若：

   $$f(n) = \Theta(n^{\log_b a})$$

   则：

   $$T(n) = \Theta(n^{\log_b a} \log n)$$

3. 若存在常数 $\varepsilon > 0$，使得：

   $$f(n) = \Omega(n^{\log_b a + \varepsilon})$$

   且存在常数 $c < 1$，并且当 $n$ 足够大时，有：

   $$a f(n/b) \leq c f(n)$$

   （或等价于 $f(n)$ 的数量级高于 $O(n^{\log_b a})$ ）

   则：

   $$T(n) = \Theta(f(n))$$

---

若 $f(n)=\Theta(n^m)$ ，则

$$T(n)= \begin{cases} \Theta(n^m)&&a<b^m\\ \Theta(n^m \log n)&&a=b^m\\ \Theta(n^{\log_b a})&&a>b^m \end{cases}$$

贪心

贪心法设计求解的核心问题是：选择能产生问题最优解的量度标准，即最优量度标准。

• 缺点：

  • 不是对所有问题都能得到最优解

  • 基于目标函数制定的度量标准不一定是最优的

  • 最优量度标准需要经过证明

• 优点：

  • 一旦证明成立后，它就是一种高效的算法

  • 策略的构造简单易行

  • 对许多问题都能产生整体最优解或者近似最优解

小数背包

每个物品的价值是 $p_i$ ，可以将每个物品的一部分 $0\le x_i\le1$ 放入背包，在满足 $\sum w_ix_i\le M$的情况下最大化 $\sum p_i x_i$ 。

只需要按价值和重量比值降序排序，选取物品直到背包装满。

作业调度

假定只能在一台机器上处理$n$个作业, 每个作业均可在单位时间内完成； 又假定每个作业$i$都有一个截止期限$d_i>0$($d_i$是整数)，当且仅当作业$i$在它的期限截止之前被完成时获得$p_i>0$的效益。

以目标函数$\sum p_j$作为量度标准, 将各作业按效益$p_i$降序排列： $p_1\ge p_2\ge …\ge p_n$ 。