算法分析与设计

概念

算法的定义

给定计算问题，算法是一系列良定义（没有歧义）的计算步骤，逐一执行计算步骤即可得预期的输出。

算法的性质：有穷性、确定性、可行性

• 有穷性：算法必须在有限个计算步骤后终止。
• 确定性：算法必须是没有歧义的。
• 可行性：可以机械地一步一步执行基本操作步骤。

算法的表示

自然语言、机器语言、伪代码（推荐）。

例如，插入排序的伪代码可以表示如下：

for j<-2 to n do
	key<-A[j]
	while i>0 and A[i]>key do
		A[i+1]<-A[i]
		i<-i-1
	end
end

选择排序的伪代码可以表示如下：

for i<-1 to n-1 do
	cur_min<-A[i]
	cur_min_pos<-i
	for j<-i+1 to n do
		if A[j]<cur_min_pos then
			cur_min<-A[j]
			cur_min_pos<-j
		end
	end
	交换 A[i] 和 A[cur_min_pos]
end

算法的分析

算法分析的原则

• 统一机器性能
• 分析最坏情况

这样，算法运行时间仅依赖于问题输入规模 $n$ ，表示为 $T(n)$ 。

算法分析的工具——时间复杂度

计算每行伪代码操作次数并求和。例如，插入排序的 $T(n)= \frac{3}{2}n^2+\frac{7}{2}n-4$ ，选择排序的 $T(n)=2n^2+3n-4$ 。

渐近分析：分析 $n$ 充分大时函数的大小关系（忽略 $T(n)$ 的系数与低阶项，仅关注高阶项），并用渐近记号表示。

• 渐近紧确界：用记号 $\theta$ 表示。对于给定的函数 $g(n)$ ，$\theta(g(n))$ 表示以下函数的集合：$\theta(g(n))=\{ T(n):\exists c_1,c_2,n_0>0,使得\forall n\geq n_0,c_1g(n)\leq T(n)\leq c_2g(n)\}$。$T(n)$ 的上界 $c_1g(n)$ 即是 $O$ ，下界即是 $\Omega$ 。

• 渐近上界：用记号 $O$ 表示。对于给定的函数 $g(n)$ ，$O(g(n))$ 表示以下函数的集合：$O(g(n))=\{T(n):\exists c,n_0>0,使得\forall n\geq n_0,0\leq T(n)\leq cg(n)\}$ 。

• 渐近下界：用记号 $\Omega$ 表示。对于给定的函数 $g(n)$ ，$\Omega(g(n))$ 表示以下函数的集合：$\Omega(g(n))=\{T(n):\exists c,n_0>0,使得\forall n\geq n_0, 0\leq cg(n)\leq T(n)\}$ 。

$T(n)=\theta(g(n))$ 等价于：$T(n)=\Omega(g(n))$ 且 $T(n)=\Omega(g(n))$ 。

算法运行时间称为算法时间复杂度，通常使用渐近记号 $O$ 表示。例如，插入排序的时间复杂度为 $O(n^2)$ ，选择排序的时间复杂度同样为 $O(n^2)$ 。

分而治之法

归并排序

之前的排序方法简述：

选择排序：从待排序元素中迭代选出最小值并排序。

插入排序：依次将每个元素插入到已排序序列之中。

算法流程：分解数组->递归求解->合并排序

• 分解数组：将数组$A[1,n]$排序问题分解为 $A[1,\lfloor \frac{n}{2} \rfloor]$ 和 $A[\lfloor \frac{n}{2} \rfloor+1,n]$ 排序问题。
• 递归求解：递归解决子问题得到两个有序的子数组
• 合并排序：将两个有序子数组合并为一个有序数组

归并排序算法的步骤即分而治之法的一般步骤：分解原问题->解决子问题->合并问题解。

伪代码

归并排序算法伪代码如下：

复杂度分析

$T(n)$：完成 $MergeSort(A,1,n)$ 的运行时间。

为便于分析，假设 $n$ 是2的幂。

可以得出递归关系式：

$T(n)=\left\{ \begin{array}{lr}  2T(n/2)+O(n), & if\  n>1 \\ O(1), & if\  n=1 \end{array} \right.$

递归树法：用树的形式表示抽象递归。

递归式分析方法：递归树法、代入法（猜测+数学归纳法证明）、主定理法。【详见高数，这里不提了】

最大子数组问题

问题定义

输入：给定一个数组$X[1..n]$，对于任意一对数组下标为 $l,r(l\leq r)$ 的非空子数组，其和记为

$S(l,r)=\sum_{i=l}^rX[i]$

输出：求出 $S(l,r)$ 的最大值，记为 $S_{max}$ 。

蛮力枚举法

枚举 $n+C_n^2$ 种可能的区间 $[l,r](l \leq r)$ ，求解最大子数组之和 $S_{max}$ 。

伪代码如下：

时间复杂度：$O(n^3)$

缺点：重复计算，效率低

优化枚举

利用已有的子数组和继续计算下一组子数组和。

核心思想：$S(l,r)=\sum_{i=l}^rX[i]=S(l,r-1)+X[r]$。

伪代码如下：

时间复杂度：$O(n^2)$

分而治之

一般步骤：

• 将数组 $X[1..n]$ 分为 $X[1..n/2]$ 和 $X[n/2+1..n]$
• 递归求解子问题
  • $S_1$：数组 $X[1..n/2]$ 的最大子数组
  • $S_2$：数组 $X[n/2+1..n]$ 的最大子数组
• 合并子问题，得到$S_{max}$
  • $S_3$：跨中点的最大子数组
  • 数组 $X$ 的最大子数组之和 $S_{max}=max\{S_1,S_2,S_3\}$

如何求解$S_3$：

• 记$mid=n/2$
• $S_3$可以分为左右两部分
  • $Left$：以 $X[mid]$ 为结尾的最大子数组之和
  • $Right$：以 $X[mid+1]$ 为开头的最大子数组之和
  • $S_3=Left+Right$
• 求解$Left$
  • 记 $mid=n/2$
  • 从 $X[mid]$ 向前遍历求和，并记录最大值
  • 以 $X[mid]$ 为结尾的最大子数组之和 $S_{left}=4$
• 求解$Right$
  • 记 $mid=n/2$
  • 从 $X[mid+1]$ 向后遍历求和，并记录最大值
• 时间复杂度：$T(n)=T(Left)+T(Right)=O(mid)+O(n-mid)=O(n)$

求解 $S_3$ 的伪代码如下：

分而治之算法伪代码如下：

时间复杂度分析：

• 输入规模：$n$

• $T(n)=\left\{ \begin{array}{lr}  1, & n=1 \\ 2\cdot T(n/2)+O(n), & n >1 \end{array} \right.$

• 时间复杂度 $O(n\log n)$