算法导论 学习笔记

基础知识

算法基础

增量方法

插入排序

1
2
3
4
5
6
7
8

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[j] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

循环不变式

循环不变式主要用来帮助我们理解算法的正确性。关于循环不变式，我们必须证明三条性质：

• 初始化：循环的第一次迭代之前，它为真
• 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍然为真
• 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的

分治法

分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解
分治模式在每层递归时都有三个步骤：

• 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例
• 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解
• 合并这些子问题的解成原问题的解

归并排序

• 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
• 解决：使用归并排序递归地排序两个子序列
• 合并：合并两个已排序的子序列以产生已排序的答案

我们通过调用一个辅助过程 MERGE(A, p, q, r) 来完成合并，其中$A$是一个数组， $p$、$q$和$r$是数组下标，满足$p \leq q < r$。该过程假设子数组$A[p..q]$和$A[q+1..r]$都已排好序
过程 MERGE 需要$\Theta(n)$的时间，其中$n=r-p+1$是带合并元素的总数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i = i + 1
    else 
        A[k] = R[j]
        j = j + 1

1
2
3
4
5
6

MERGE-SORT(A, p, r)
if p < r
    q = ⌊(p + r)/2⌋
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q+1, r)
    MERGE(A, p, q, r)

分析分治算法

假设$T(n)$是规模为$n$的一个问题的运行时间：

• 若问题规模足够小，则直接求解需要常量时间$\Theta(1)$
• 假设把原问题分解为$a$个子问题，每个子问题的规模是原问题的$1/b$。为了求解一个规模为$n/b$的子问题，需要$T(n/b)$的时间，所以需要$aT(n/b)$的时间来求解$a$个子问题
• 分解问题成子问题需时间$D(n)$
• 合并子问题的解成原问题的解需时间$C(n)$

那么得到递归式：

$$T(n) = \begin{cases} \Theta(1) \qquad & n \leq c \\ aT(n/b)+D(n)+C(n) \qquad & other \end{cases}$$

对于归并排序，其最坏情况运行时间$T(n)$的递归式：

$$T(n) = \begin{cases} \Theta(1) \qquad & n = 1 \\ 2T(n/2)+\Theta(n) \qquad & n>1 \end{cases} = \Theta(nlgn)$$

函数增长

渐进记号

$\Theta$记号

对于一个给定的函数$g(n)$，用$\Theta(g(n))$来表示以下函数的集合：
$\Theta(g(n))=\{f(n):\text{存在正常量}c_1\text{、}c_2\text{和}n_0\text{，使得对所有}n \geq n_0\text{，有}0\leq c_1g(n) \leq f(n) \leq c_2g(n)\}$

我们称$g(n)$是$f(n)$的一个渐进紧确界

$O$记号

对于一个给定的函数$g(n)$，用$O(g(n))$来表示以下函数的集合：
$O(g(n))=\{f(n):\text{存在正常量}c\text{和}n_0\text{，使得对所有}n \geq n_0\text{，有}0\leq f(n) \leq cg(n)\}$

我们称$g(n)$是$f(n)$的一个渐进上界

$\Omega$记号

对于一个给定的函数$g(n)$，用$\Omega(g(n))$来表示以下函数的集合：
$\Omega(g(n))=\{f(n):\text{存在正常量}c\text{和}n_0\text{，使得对所有}n \geq n_0\text{，有}0\leq cg(n) \leq f(n)\}$

我们称$g(n)$是$f(n)$的一个渐进下界

$o$记号

对于一个给定的函数$g(n)$，用$o(g(n))$来表示以下函数的集合：
$o(g(n))=\{f(n):\text{存在正常量}c\text{和}n_0\text{，使得对所有}n \geq n_0\text{，有}0\leq f(n) < cg(n)\}$
我们称$g(n)$是$f(n)$的一个非渐进紧确上界

$\omega$记号

对于一个给定的函数$g(n)$，用$\omega(g(n))$来表示以下函数的集合：
$\omega(g(n))=\{f(n):\text{存在正常量}c\text{和}n_0\text{，使得对所有}n \geq n_0\text{，有}0\leq cg(n) < f(n)\}$
我们称$g(n)$是$f(n)$的一个非渐进紧确下界

比较各种函数

• 传递性
  $f(n) = \Theta(g(n)) \land g(n) = \Theta(h(n)) \rightarrow f(n) = \Theta(h(n))$
  $f(n) = O(g(n)) \land g(n) = O(h(n)) \rightarrow f(n) = O(h(n))$
  $f(n) = \Omega(g(n)) \land g(n) = \Omega(h(n)) \rightarrow f(n) = \Omega(h(n))$
  $f(n) = o(g(n)) \land g(n) = o(h(n)) \rightarrow f(n) = o(h(n))$
  $f(n) = \omega(g(n)) \land g(n) = \omega(h(n)) \rightarrow f(n) = \omega(h(n))$
• 自反性
  $f(n) = \Theta(f(n))$
  $f(n) = O(f(n))$
  $f(n) = \Omega(f(n))$
• 对称性
  $f(n) = \Theta(g(n)) \leftrightarrow g(n) = \Theta(f(n))$
• 转置对称性
  $f(n) = O(g(n)) \leftrightarrow g(n) = \Omega(f(n))$
  $f(n) = o(g(n)) \leftrightarrow g(n) = \omega(f(n))$
• 类比
  $f(n) = O(g(n)) \rightarrow a \leq b$
  $f(n) = \Omega(g(n)) \rightarrow a \geq b$
  $f(n) = \Theta(g(n)) \rightarrow a = b$
  $f(n) = o(g(n)) \rightarrow a < b$
  $f(n) = \omega(g(n)) \rightarrow a > b$

标准记号与常用函数

多项式

对于一个$d$次渐进正的多项式$p(n)$，有：

$$p(n)=\Theta(n^d)$$

指数

任意底大于1的指数函数比任意多项式函数增长得快：

$$n^b = o(a^n),a>1$$

对数

对所有实数$a>0$，$b>0$，$c>0$和$n$，有：

$$a = b^{log_b a}$$

$$log_c(ab) = log_c a + log_c b$$

$$log_b a^n = n log_b a$$

$$log_b a = \frac{log_c a}{log_c b}$$

$$log_b(1/a) = -log_b a$$

$$log_b a = \frac{1}{log_a b}$$

$$a^{log_b c} = c^{log_b a}$$

任意正的多项式函数都比任意多底数函数增长得快：

$$lg^b n = o(n^a)$$

阶乘

斯特林近似公式：

$$n!=\sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))$$

$$n!=\sqrt{2\pi n}(\frac{n}{e})^n e^{a_n}, \frac{1}{12n+1}<a_n<\frac{1}{12n}$$

给出了一个更紧确的上界和下界：

$$n!=o(n^n)$$

$$n!=\omega(2^n)$$

$$lg(n!)=\Theta(nlgn)$$

多重函数

假设$f(n)$为实数集上的一个函数，对非负整数$i$，我们递归地定义：

$$f^{(i)}(n) = \begin{cases} n \qquad & i = 1 \\ f(f^{(i-1)}(n)) \qquad & i>1 \end{cases}$$

多重对数函数

定义多重对数函数为：

$$lg*n=min\{i \geq 0:lg^{(i)}n \leq 1\}$$

多重对数是一个增长非常慢的函数:

• $lg*2=1$
• $lg*4=2$
• $lg*16=3$
• $lg*65536=4$
• $lg*(2^{65536})=5$

分治策略

• 代入法：我们猜测一个界，然后用数学归纳法证明这个界是正确的
• 递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式
• 主方法：可求解形如下面公式的递归式的界：

$$T(n)=aT(n/b)+f(n),a\geq 1,b>1$$

最大子数组问题

寻找A的和最大的非空连续子数组，这样的连续子数组为最大子数组

使用分治策略的求解方法

$A[low..high]$的任何连续子数组$A[i..j]$所处的位置必然是一下三种情况之一：

• 完全位于子数组$A[low..mid]$中，因此$low \leq i \leq j \leq mid$
• 完全位于子数组$A[mid+1..high]$中，因此$mid < i \leq j \leq high$
• 跨越了中点，因此$low \leq i \leq mid < j \leq high$

过程 FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) 接收数组$A$和下标$low$，$mid$和$high$为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -∞
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

1
2
3
4
5
6
7
8
9
10
11
12

FIND-MAXINUM-SUBARRAY(A, low, high)
if high == low
    return (low, high, A[low])
else mid = ⌊(low + high)/2⌋
    (left-low, right-high, left-sum) = FIND-MAXINUM-SUBARRAY(A, low, mid)
    (right-low, right-high, right-sum) = FIND-MAXINUM-SUBARRAY(A, mid+1, high)
    (cross-low, cross-high, cross-zum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
    if left-sum >= right-sum and left-sum >= cross-sum
        return (left-low, left-high, left-sum)
    elseif right-sum >= left-sum and right-sum >= cross-sum
        return (right-low, right-high, right-sum)
    else return (cross-low, cross-high, cross-sum)

分治算法的分析

FIND-MAXINUM-SUBARRAY 运行时间$T(n)$的递归式：

$$T(n) = \begin{cases} \Theta(1) \qquad & n = 1 \\ 2T(n/2) + \Theta(n) \qquad & n>1 \end{cases} = \Theta(nlgn)$$

矩阵乘法的Strassen算法

基础的矩阵乘法

复杂度 $\Theta (n^3)$

1
2
3
4
5
6
7
8
9

SQUARE-MATRIX-MULTIPLY(A, B)
n = A.rows
let C be a new n * n matrix
for i = 1 to n
    for j = 1 to n
        c_ij = 0
        for k = 1 to n
            c_ij = c_ij + a_ik * b_kj
return C

简单的分治算法

假定将$A$，$B$和$C$均分解为4个$n/2 \times n/2$的子矩阵：

$$A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} , B = \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} , C = \begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix}$$

可以将公式$C = A \cdot B$改写为：

$$\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \cdot \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}$$

1
2
3
4
5
6
7
8
9
10

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A, B)
n = A.rows
let C be a new n * n matrix
if n == 1
    c_11 = a_11 * b_11
else partition A, B and C as in equations 
    C_11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11, B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12, B_21)
    C_12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11, B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12, B_22)
    C_21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21, B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22, B_21)
    C_22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21, B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22, B_22)

SQUARE-MATRIX-MULTIPLY-RECURSIVE 运行时间$T(n)$的递归式：

$$T(n) = \begin{cases} \Theta(1) \qquad & n = 1 \\ 8T(n/2) + \Theta(n^2) \qquad & n>1 \end{cases} = \Theta(n^3)$$

Strassen方法

Strassen运行时间$T(n)$的递归式：

$$T(n) = \begin{cases} \Theta(1) \qquad & n = 1 \\ 7T(n/2) + \Theta(n^2) \qquad & n>1 \end{cases} = \Theta(n^{lg_7})$$

代入法求解递归式

代入法求解递归式分为两步：

• 猜测解的形式
• 用数学归纳法求出解的常数，并证明解是正确的

例如，确定下列递归式的上界：

$$T(n)=2T(\lfloor n/2 \rfloor)+n$$

猜测其解为$T(n)=O(nlgn)$
首先假定次上界对所有正数$m<n$都成立，特别对于$m=\lfloor n/2 \rfloor$，有$T(\lfloor n/2 \rfloor) \leq c\lfloor n/2 \rfloor lg(\lfloor n/2 \rfloor)$。将其带入递归式，有：

$T(n) \leq 2(c\lfloor n/2 \rfloor lg(\lfloor n/2 \rfloor)) + n \leq cn lg(n/2) + n \\ = cnlgn-cnlg2+n\\ =cnlgn-cn+n\\ \leq cnlgn$
其中，只要$c \leq 1$，最后一步都会成立

递归树求解递归式

在递归树中，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用
我们将树中的每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价

主方法求解递归式

令$a\leq 1$和$b>1$是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式：

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

• 若对某个常数$\epsilon >0$有$f(n)=O(n^{log_ba-\epsilon})$，则$T(n)=\Theta(n^{log_ba})$
• 若对于某个常数$k\geq 0$有$f(n)=\Theta(n^{log_ba}lg^kn)$，则$T(n)=\Theta(n^{log_ba}lg^{k+1}n)$
• 若对某个常数$\epsilon >0$有$f(n)=\Omega(n^{log_ba+\epsilon})$，且对某个常数$c<1$和所有足够大的$n$有$af(n/b) \leq cf(n)$，则$T(n)=\Theta(f(n))$

随机算法

雇佣问题

1
2
3
4
5
6
7

HIRE-ASSISTANT(n)
best = 0
for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

最坏情况分析

在最坏情况下，当应聘者质量按出现的次序严格递增时，总费用是$O(c_hn)$

随机算法

如果一个算法的行为不仅由输入决定，而且也由随机数生成器产生的数值决定，则称这个算法是随机的

指示器随机变量

给定一个样本空间$S$和一个事件$A$，那么事件$A$对应的指示器随机变量$I\{A\}$定义为：

$$I\{A\} = \begin{cases} 1 \qquad & if\ A \ occurs \\ 0 \qquad & if \ A \ does\ not\ occur \end{cases}$$

给定一个样本空间$S$和$S$中的一个事件$A$，设$X_A=I\{A\}$，那么$E[X_A]=Pr\{A\}$

用指示器随机变量分析雇佣问题

应聘者$i$比应聘者1到$i-1$更有资格的概率为$1/i$
$E[X_i]=1/i$
所以有：
$E[X]\\ =E[\sum_{i=i}^n X_i]\\ = \sum_{i=1}^nE[X_i]\\ =\sum_{i=1}^n1/i\\ =lnn+O(1)$
算法 HIRE-ASSISTANT 总的雇佣费用平均情形下为$O(c_hlnn)$

随机算法

过程 RANDOMIZED-HIRE-ASSISTANT 的雇佣费用期望是$O(c_hlnn)$：

1
2
3
4
5
6
7
8

RANDOMIZED-HIRE-ASSISTANT(n)
randomly permute the list of candidates
best = 0
for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

随机排列数组

假设所有优先级都不同，则过程 PERMUTE-BY-SORTING 产生输入的均匀随机排列：

1
2
3
4
5
6

PERMUTE-BY-SORTING(A)
n = A.length
let P[1..n] be a new array
for i = 1 to n
    P[i] = RANDOM(1, n^3)
sort A, using P as sort keys

过程 RANDOMIZE-IN-PLACE 可计算出一个均匀随机排列：

1
2
3
4

RANDOMIZE-IN-PLACE(A)
n = A.length
for i = 1 to n
    swap A[i] with A[RANDOM(i, n)]

排序和顺序统计量

堆排序

堆

堆是一个数组，它可以被看成一个近似的完全二叉树

• 树上的每一个结点对应数组中的一个元素
• 除了最底层外，该树是完全充满的
• $A.length$表示数组元素的个数
• $A.heap-size$表示有多少个堆元素存储在该数组中
• $0 \leq A.heap-size \leq A.length$
• 一个堆中的结点的高度就为该结点到叶结点最长简单路径上边的数目

计算父结点、左孩子和右孩子的下标：

1
2
3
4
5
6
7
8

PARENT(i)
    return ⌊i/2⌋

LEFT(i)
    return 2i

RIGHT(i)
    return 2i + 1

在最大堆中，最大堆性质指除了根以外的所有结点$i$都要满足：

$$A[PARENT(i)] \geq A[i]$$

在最小堆中，最小堆性质指除了根以外的所有结点$i$都要满足：

$$A[PARENT(i)] \leq A[i]$$

维护堆的性质

假定根结点为 LEFT(i) 和 RIGHT(i) 的二叉树都是最大堆，MAX-HEAPIFY 通过让$A[i]$的值在最大堆中“逐级下降”，从而使得以下标$i$为根结点的子树重新遵循最大堆的性质：

1
2
3
4
5
6
7
8
9
10
11
12

MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size and A[l] > A[i]
    largest = l
else
    largest = i
if r <= A.heap-size and A[r] > A[largest]
    largest = r
if largest != i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A, largest)

因为每个孩子的子树的大小至多为$2n/3$（最坏情况发生在树的最底层恰好半满的时候），我们可以用下面递归式刻画 MAX-HEAPIFY 的运行时间：

$$T(n) \leq T(2n/3)+\Theta(1) = O(lgn) = O(h)$$

建堆

可以用自底向上的方法利用过程 MAX-HEAPIFY 把一个大小为$n=A.length$的数组$A[1..n]$转换为最大堆：

1
2
3
4

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = ⌊A.length/2⌋ downto  1
    MAX-HEAPIFY(A, i)

在一个高度为$h$的结点上运行 MAX-HEAPIFY 的代价是$O(h)$，我们可以将 BUILD-MAX-HEAP 的总代价表示为：

$$\sum^{\lfloor lgn \rfloor}_{h=0} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O(n \sum^{\lfloor lgn \rfloor}_{h=0} \frac{h}{2^h}) = O(n \sum^{\infty}_{h=0} \frac{h}{2^h}) =O(n)$$

因此，我们可以在线性时间内，把一个无序数组构造成一个最大堆

堆排序算法

HEAPSORT 过程的时间复杂度是$O(nlgn)$：

1
2
3
4
5
6

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)

优先队列

优先队列是一种用来维护由一组元素构成的集合$S$的数据结构，其中的每一个元素都有一个相关的值，称为关键字。一个最大优先队列支持以下操作：

• INSERT(S, x)：把元素$x$插入集合$S$中
• MAXIMUM(S)：返回$S$中具有最大键字的元素
• EXTRACT-MAX(S)：去掉并返回$S$中的具有最大键字的元素
• INCREASE-KEY(S, x, k)：将元素$x$的关键字增加到$k$，这里假设$k$的值不小于$x$的原关键字值

优先队列可以用堆来实现：
HEAP-MAXMIUM 时间复杂度$\Theta(1)$：

1
2

HEAP-MAXMIUM(A)
    return A[1]

HEAP-EXTRACT-MAX 时间复杂度$O(lgn)$：

1
2
3
4
5
6
7
8

HEAP-EXTRACT-MAX(A)
if A.heap-size <  1 
    error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max

HEAP-INCREASE-KEY 时间复杂度$O(lgn)$：

1
2
3
4
5
6
7

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
    error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)

MAX-HEAP-INSERT 时间复杂度$O(lgn)$：

1
2
3
4

MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = -∞
HEAP-INCRERASE-KEY(A, A.heap-size, key)

快速排序

快速排序描述

对一个子数组$A[p..r]$进行快速排序的三步分治过程：

• 分解：数组$A[p..r]$被划分为两个（可能为空）子数组$A[p..q-1]$和$A[q+1..r]$，使得$A[p..q-1]$中的每一个元素都小于等于$A[q]$，而$A[q]$也小于等于$A[q+1..r]$中的每个元素。其中，计算下标$q$也是划分过程的一部分
• 解决：通过递归调用快速排序，对子数组$A[p..q-1]$和$A[q+1..r]$进行排序
• 合并：因为子数组都是原址排序的，所以不需要合并操作：数组$A[p..r]$已经有序

1
2
3
4
5

QUICKSORT(A, p, r)
if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q-1)
    QUICKSORT(A, q+1, r)

PARTITION 过程实现了对子数组$A[p..r]$的原址重排：

1
2
3
4
5
6
7
8
9

PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r-1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i+1

快速排序性能

最坏情况划分

当划分产生的两个子问题分别包含了$n-1$个元素和0个元素时，为最坏情况
此时算法递归式可以表示为：

$$T(n)=T(n-1)+T(0)+\Theta(n) =T(n-1) + \Theta(n) = \Theta(n^2)$$

最好情况划分

在可能的最平衡的划分中，PARTITION 得到的两个子问题的规模都不大于$n/2$
此时算法递归式可以表示为：

$$T(n)=2T(n/2)+\Theta(n)=\Theta(nlgn)$$

平衡的划分

任何一种常数比例的划分都会产生深度为$\Theta(lgn)$的递归树，其中每一层的时间代价都是$O(n)$
因此，只要划分是常数比例的，算法的运行时间总是$O(nlgn)$

对于平均情况的直观观察

当好和差的划分交替出现时，快速排序的时间复杂度与全是好的划分时一样，仍然是$O(nlgn)$。区别只是$O$符号中隐含的常数因子要略大一些

快速排序随机化版本

通过对序列$p,..,r$的随机抽样，我们期望在平均情况下，对输入数组的划分是比较均衡的：

1
2
3
4

RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)

1
2
3
4
5

RANDOMIZED-QUICKSORT(A, p, r)
if p < r
    q = RANDOMIZED-PARTITION(A, p, r)
    RANDOMIZED-QUICKSORT(A, p, q-1)
    RANDOMIZED-QUICKSORT(A, q+1, r)

快速排序分析

最坏情况分析

快速排序的最坏情况运行时间是$\Theta(n^2)$

期望运行时间

快速排序的期望运行时间是$O(nlgn)$

线性时间排序

排序算法的下界

决策树模型

比较排序可以被抽象为一棵决策树
决策树是一棵完全二叉树，它可以表示在给定输入规模情况下，某一给定排序算法对所有元素的比较操作
在决策树中，每个内部结点都以$i:j$标记，其中$i$和$j$满足$1 \leq i,j \leq n$，$n$是输入序列中的元素个数
每一个内部结点表示一次比较$a_i \leq a_j$

• 左子树表示一旦我们确定$a_i \leq a_j$之后的后续比较
• 右子树表示一旦我们确定$a_i > a_j$之后的后续比较

对于一个正确的比较排序算法来说，$n$个元素的$n!$种可能的排列都应该出现在决策树的叶结点上。而且，每一个叶结点都必须是可以从根结点经由某条路径到达的

最坏情况的下界

在最坏情况下，任何比较排序算法都需要做$\Omega(nlgn)$次比较：
考虑一棵高度为$h$，具有$l$个可达叶结点的决策树，它对应一个对$n$个元素所做的比较排序。因为输入数据的$n!$种可能的排列都是叶结点，所以有$n! \leq l$。由于在一个高度为$h$的二叉树中，叶结点的数目 不多于$2^h$，所以有：

$$n! \leq l \leq 2^h$$

对该式两边取对数，有$h \geq lg(n!) = \Omega(nlgn)$

计数排序

计数排序假设$n$个输入元素中的每一个都是在0到$k$区间内的一个整数，其中$k$为某个整数。当$k=O(n)$时，排序的运行时间为$\Theta(n)$

在计数排序的代码中，假设输入是一个数组$A[1..n]$，$A.length = n$，$B[1..n]$存放排序的输出，$C[0..k]$提供临时存储空间：

1
2
3
4
5
6
7
8
9
10
11

COUNTING-SORT(A, B, k)
let C[0..k] be a new array
for i = 0 to k
    C[i] = 0
for j = 1 to A.length
    C[A[j]] = C[A[j]] + 1
for i = 1 to k
    C[i] = C[i-1] + C[i]
for j = A.length downto 1
    B[C[A[j]]] = A[j]
    C[A[j]] = C[A[j]] - 1

计数排序时间复杂度$\Theta(k+n)$，当$k=O(n)$时，时间复杂度$\Theta(n)$

基数排序

假设$n$个$d$位的元素存放在数组$A$中，其中第1位是最低位，第$d$位是最高位：

1
2
3

RADIX-SORT(A, d)
for i = 1 to d
    use a stable sort to sort array A on digit i

给定一个$b$位数和任何正整数$r\leq b$，如果 RADIX-SORT 使用的稳定排序算法对数据取值区间是0到$k$的输入进行排序耗时$\Theta(n+k)$，那么它就可以在$\Theta((b/r)(n+2^r))$时间内将这些数据排好序

桶排序

桶排序假设输入数据服从均匀分布，平均情况下它的时间代价为$O(n)$

假设输入是一个包含$n$个元素的数组$A$，且每个元素$A[i]$满足$0 \leq A[i] < 1$。算法还需要一个临时数组$B[0..n-1]$来存放链表（即桶），并假设存在一种用于维护这些链表的机制：

1
2
3
4
5
6
7
8
9
10

BUCKET-SORT(A)
n = A.length
let B[0..n-1] be a new array
for i = 0 to n-1
    make B[i] an empty list
for i = 1 to n
    insert A[i] into list B[⌊nA[i]⌋]
for i = 0 to n-1
    sort list B[i] with insertion sort
concatenate the lists B[0]..B[n-1] together in order

桶排序的期望运行时间为：

$$\Theta(n)+n \cdot O(2-1/n) = \Theta(n)$$

中位数和顺序统计量

最小值和最大值

假设该集合元素存放在数组$A$中，且$A.length = n$：

1
2
3
4
5
6

MINIMUM(A)
min = A[1]
for i = 2 to A.length
    if min > A[i]
        min = A[i]
return min

为了确定最小值，必须要做$n-1$次比较

同时找到最小值和最大值

最多$3\lfloor n/2 \rfloor$次比较就可以同时找到最小值和最大值：
首先，我们将一对输入元素相互进行比较，然后把较小的与当前最小值比较，把较大的与当前最大值进行比较。这样，对每两个元素共需3次比较：

• 如果$n$是奇数，我们就将最小值和最大值的初值设为第一个元素的值，然后成对地处理余下的元素
• 如果$n$是偶数，就对前两个元素做一次比较，以决定最小值和最大值的初值，然后成对处理余下的元素

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

RANDOMIZED-SELECT 返回数组$A[p..r]$中第$i$小的元素：

1
2
3
4
5
6
7
8
9
10
11

RANDOMIZED-SELECT(A, p, r, i)
if p == r
    return A[p]
q = RANDOMIZE-PARTITOOPN(A, p, r)
k = q - p + 1
if i == k
    return A[q]
else if i < k
    return RANDOMIZED-SELECT(A, p, q-1, r)
else 
    return RANDOMIZED-SELECT(A, q+1, r, i-k)

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

最坏情况为线性时间的选择算法

通过执行下列步骤，算法 SELECT 可以确定一个有$n>1$个不同元素的输入数组中的第$i$小的元素

• 将输入数组的$n$个元素划分为$\lfloor n/5 \rfloor$组，每组5个元素，且至多只有一组由剩下的$n \ mod \ 5$个元素组成
• 寻找这$\lceil n/5 \rceil$组中每一组的中位数：首先对每组元素进行插入排序，然后确定每组有序元素的中位数
• 对第2步中找出的$\lceil n/5 \rceil$个中位数，递归调用 SELECT 以找出其中位数$x$（如果有偶数个中位数，为了方便，约定$x$是较小的中位数）
• 利用修改过的 PARTITION 版本，按中位数的中位数$x$对输入数组进行划分。让$k$比划分的低区中的元素数目多1，因此$x$是第$k$小的元素，并且有$n-k$个元素在划分的高区
• 如果$i=k$，则返回$x$。如果$i<k$，则在低区递归调用 SELECT 来找出第$i$小的元素。如果$i>k$，则在高区递归查找第$i-k$小的元素

在第2步找出的中位数中，至少有一半大于或等于中位数的中位数$x$。因此，在这$\lceil n/5 \rceil$个组中，除了当$n$不能被5整除时产生的所含元素少于5的那个组和包含$x$的那个组之外，至少有一半的组中有3个元素大于$x$。不算这两个组，大于$x$的元素个数至少为：

$$3(\lceil \frac{1}{2} \lceil \frac{n}{5} \rceil\rceil - 2) \geq \frac{3n}{10}-6$$

类似地，至少有$3n/10-6$个元素小于$x$。因此，在最坏情况下，在第5步中，SELECT 的递归调用最多作用于$7n/10+6$个元素。
由此可以得到如下递归式：

$$T(n) \leq \begin{cases} \Theta(1) \qquad & n < 140 \\ T(\lceil n/5 \rceil) + T(7n/10+6) + O(n) \qquad & n\geq 140 \end{cases} = O(n)$$

高级设计和分析技术

动态规划

我们通常按如下4个步骤来设计一个动态规划算法：

• 刻画一个最优解的结构特征
• 递归地定义最优解的值
• 计算最优解的值，通常采用自底向上的方法
• 利用计算出的信息构造一个最优解

钢条切割

给定一段长度为$n$英寸的钢条和一个价格表$p_i(i=1,2,...,n)$，求切割钢条方案，使得销售收益$r_n$最大

自顶向下 CUT-ROD过程，加入了备忘机制，时间复杂度$\Theta(n^2)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

MEMORIZED-CUT-ROD(p, n)
let r[0..n] be a new array
for i = 0 to n
    r[i] = -∞
return MEMORIZED-CUT-ROD-AUX(p, n, r)

MEMORIZED-CUT-ROD-AUX(p, n, r)
if r[n] >=0
    return r[n]
if n == 0
    q = 0
else 
    q = -∞
    for i = 1 to n
    q = max(q, p[i] + MEMORIZED-CUT-ROD-AUX(p, n-i, r))
r[n] = q
return q

自底向上版本，时间复杂度$\Theta(n^2)$：

1
2
3
4
5
6
7
8
9

BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        q = max(q, p[i] + r[j-i])
    r[j] = q
return r[n]

重构解

BOTTOM-UP-CUT-ROD 的扩展版本，它对长度为$j$的钢条不仅计算最大收益值$r_j$，还保存最优解对应的第一段钢条的切割长度$s_j$：

1
2
3
4
5
6
7
8
9
10
11

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] and s[0..n] be new arrays
r[0] = 0
for j = 1 to n
    q = -∞
    for i = 1 to j
        if q < p[i] + r[j-i]
            q = p[i] + r[j-i]
            s[j] = i
    r[j] = q
return r and s

最后输出长度为$n$的钢条的完整的最优切割方案：

1
2
3
4
5

PRINT-CUT-ROD-SOLUTION(p, n)
(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
while n > 0
    print s[n]
    n = n - s[n]

矩阵链乘法

给定一个$n$个矩阵的序列（矩阵链）$\langle A_1,A_2,...,A_n\rangle$，我们希望计算它们的乘积：

$$A_1A_2...A_n$$

由于矩阵乘法满足结合律，因此任何加括号的方法都会得到相同的计算结果

我们称有如下性质的矩阵乘积链为完全括号化的：它是单一矩阵，或者是两个完全括号化的矩阵乘积链的积
给定$n$个矩阵的链$\langle A_1,A_2,...,A_n\rangle$，矩阵$A_i$的规模为$p_{i-1} * p_i(1 \leq i \leq n)$，求完全括号化方案，使得计算乘积$A_1A_2...A_n$所需标量乘法次数最少

令$m[i,j]$表示计算矩阵$A_{i..j}$所需标量乘法次数的最小值，则$A_iA_{i+1}...A_j$最小代价括号化方案的递归求解公式为：

$$m[i,j] \leq \begin{cases} 0 \qquad & i = j \\ min_{i \leq k < j}\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\} \qquad & i <j \end{cases}$$

MATRIX-CHAIN-ORDER 时间复杂度$O(n^3)$，另外还需要$\Theta(n^2)$的内存空间来保存表$m$和$s$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

MATRIX-CHAIN-ORDER(p)
n = p.length - 1
let m[1..n,1..n] and s[1..n-1,2..n] be new tables
for i = 1 to n
    m[i,i] = 0
for l = 2 to n  //l is the chain length
    for i = 1 to n-l+1
        j = i + l - 1
        m[i,j] = ∞
        for k = i to j-1
            q = m[i, k] + m[k+1, j] + p_i-1p_kp_j
            if q < m[i,j]
                m[i,j] = q
                s[i,j] = k
return m and s

调用 PRINT-OPTIMAL-PARENS 可输出$\langle A_1,A_2,...,A_n\rangle$的最优括号化方案：

1
2
3
4
5
6
7
8

PRINT-OPTIMAL-PARENS(s, i, j)
if i == j
    print "A"
else 
    print "("
    PRINT-OPTIMAL-PARENS(s, i, s[i,j])
    PRINT-OPTIMAL-PARENS(s, s[i,j]+1, j)
    print ")"

最长公共子序列（LCS）

给定一个序列$X = \langle x_1,x_2...x_m\rangle$，令一个序列$Z=\langle z_1,z_2,...,z_k\rangle$满足如下条件时称为$X$的子序列：存在一个严格递增的$X$的下标序列$\langle i_1,i_2,...,i_k\rangle$，对所有$j=1,2,...,k$，满足$x_i=z_j$
给定两个序列$X = \langle x_1,x_2...x_m\rangle$和$Y =\langle y_1,y_2,...,y_n\rangle$，求$X$和$Y$长度最长的公共子序列

我们定义$c[i,j]$表示$X_i$和$Y_j$的 LCS 的长度，可得如下公式：

$$c[i,j] \leq \begin{cases} 0 \qquad & i = 0 \lor j = 0 \\ c[i-1,j-1]+1 \qquad & i,j >0 \land x_i = y_i \\ max(c[i,j-1],c[i-1,j]) & i,j >0 \land x_i \neq y_i \end{cases}$$

LCS-LENGTH 时间复杂度$\Theta(mn)$：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

LCS-LENGTH(X, Y)
m = X.length
n = Y.length
let b[1..m,1..n] and c[0..m,0..n] be new tables
for i = 1 to m
    c[i,0] = 0
for j = 0 to n
    c[0,j] = 0
for i = 1 to m
    for j = 1 to n
        if xi == yj
            c[i,j] = c[i-1,j-1] + 1
            b[i,j] = "↖"
        elseif c[i-1,j] >= c[i,j-1]
            c[i,j] = c[i-1,j]
            b[i,j] = "↑"
        else 
            c[i,j] = c[i,j-1]
            b[i,j] = "←"
return c and b

调用 PRINT-LCS 可打印出$X$和$Y$的一个 LCS：

1
2
3
4
5
6
7
8
9
10

PRINT-LCS(b, X, i, j)
if x == 0 or j == 0
    return
if b[i,j] == "↖"
    PRINT-LCS(b, X, i-1, j-1)
    print xi
elseif b[i,j] == "↑"
    PRINT-LCS(b, X, i-1, j)
else
    PRINT-LCS(b, X, i, j-1)

最优二叉搜索树

给定一个$n$个不同关键字的已排序的序列$K=\langle k_1,k_2,...,k_n \rangle ,k_1<k_2<...<k_n$，我们希望用这些关键字构造一棵二叉搜索树，对每个关键字$k_i$，都有一个概率$p_i$表示其搜索频率。有些要搜索的值可能不在$K$中，因此我们还有$n+1$个“伪关键字”$d_0,d_1,...,d_n$表示不在$K$中的值。$d_0$表示所有小于$k_1$的值，$d_n$表示所有大于$k_n$的值，对$i=1,2,...,n-1$，伪关键字$d_i$表示所有在$k_i$和$k_{i+1}$之间的值。对每个伪关键字$d_i$，也都有一个概率$q_i$表示对应的搜索频率。每个关键字$k_i$是一个内部结点，而每个伪关键字$d_i$是一个叶结点：