算法导论 学习笔记

基础知识

算法基础

增量方法

插入排序

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$是带合并元素的总数

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

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$为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和：

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)

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)$

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}$$

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))$

随机算法

雇佣问题

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)$：

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 产生输入的均匀随机排列：

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 可计算出一个均匀随机排列：

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$
• 一个堆中的结点的高度就为该结点到叶结点最长简单路径上边的数目

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

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$为根结点的子树重新遵循最大堆的性质：

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]$转换为最大堆：

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)$：

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)$：

HEAP-MAXMIUM(A)
    return A[1]

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

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)$：

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)$：

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]$已经有序

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]$的原址重排：

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$的随机抽样，我们期望在平均情况下，对输入数组的划分是比较均衡的：

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

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]$提供临时存储空间：

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$位是最高位：

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]$来存放链表（即桶），并假设存在一种用于维护这些链表的机制：

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$：

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$小的元素：

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)$：

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)$：

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$：

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$的钢条的完整的最优切割方案：

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$：

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$的最优括号化方案：

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)$：

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：

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$是一个叶结点：

有如下公式：

$$\sum^{n}_{i=1}p_i+\sum^n_{i=0}q_i=1$$

在$T$中进行一次搜索的期望代价为：

$$E[cost]=1+\sum^{n}_{i=1}depth_T(k_i) \cdot p_i + \sum^n_{i=0}depth_T(d_i) \cdot q_i$$

对于一个给定的概率集合。我们希望构造一棵期望搜索代价最小的二叉搜索树，我们称为最优二叉搜索树

定义$e[i,j]$为在包含关键字$k_i,...,k_j$的最优二叉搜素树中进行一次有所的期望代价，其中$i \geq i$，$j \leq n$且$j\geq i-1$（当$j=i-1$时，子树不包含实际关键字，只包含伪关键字$d_{i-1}$）

当一棵子树成为一个结点的子树时，对于包含关键字$k_i,..k_j$的子树，子树的期望搜索代价的增加值为：

$$w(i,j)=\sum^j_{l=i}p_l+\sum^j_{l=i-1}q_l$$

递归公式：

$$e[i,j] \leq \begin{cases} q_{i-1} \qquad & j=i-1 \\ min_{i \leq r \leq j}\{e[i,r-1]+e[r+1,j]+w(i,j)\} \qquad & i \leq j \end{cases}$$

OPTIMAL-BST 时间复杂度$\Theta(n^3)$：

OPTIMAL-BST(p, q, n)
let e[1..n+1,0..n],w[1..n+1,0..n] and root[1..n,1..n] be new tables
for i = 1 to n+1
    e[i,i-1] = q_{i-1}
    w[i,i-1] = q_{i-1}
for l = 1 to n
    for i = 1 to n-l+1
        j = i+l-1
        e[i,j] = ∞
        w[i,j] = w[i,j-1] + p_j +q_j
        for r = i to j
            t = e[i,r-1] + e[r+1,j] + w[i,j]
            if t < e[i,j]
                e[i,j] = t
                root[i,j] = r
return e and root

贪心算法

活动选择问题

假定有一个$n$个活动的集合$S=\{a_1,a_2,...,a_n\}$。这些活动使用同一个资源，而这个资源在某个时刻只能供一个活动使用。每个活动$a_i$都有一个开始时间$s_i$和结束时间$f_i$，其中$0\leq s_i < f_i < \infty$。如果被选中，任务$a_i$发生在半开时间区间$[s_i,f_i)$期间。如果两个活动$a_i$和$a_j$满足$[s_i,f_i)$和$[s_j,f_j)$不重叠，则称它们是兼容的

在活动选择问题中，我们希望选出一个最大兼容活动集，假定活动已按结束时间的单调递增顺序排列：

$$f_1\leq f_2 \leq .. \leq f_{n-1} \leq f_n$$

最优子结构

用$c[i,j]$表示集合$S_{ij}$的最优解的大小，则可得递归式：

$$c[i,j] \leq \begin{cases} 0 \qquad & S_{ij} = \emptyset \\ max_{a_k \in S_{ij}}\{c[i,k]+c[k,j]+1\} \qquad & S_{ij} \neq \emptyset \end{cases}$$

贪心选择

考虑任意非空子问题$S_k$，令$a_m$是$S_k$中结束时间最早的活动，则$a_m$在$S_k$的某个最大兼容活动子集中

递归贪心算法

求解原问题可调用 RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n)，在输入活动已按结束时间排序的前提下，时间复杂度$\Theta(n)$：

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)
m = k + 1
while m <= n and s[m] < f[k]
    m = m + 1
if m <= n
    return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
else
    return ∅

迭代贪心算法

在输入活动已按结束时间排序的前提下，时间复杂度$\Theta(n)$：

GREEDY-ACTIVITY-SELECTOR(s, f)
n = s.length
A = {a_1}
k = 1
for m = 2 to n
    if s[m] >= f[k]
        A = A ∪ {a_m}
        k = m
return A

霍夫曼编码

前缀码

前缀码，即没有任何码字是其他码字的前缀。前缀码可以保证达到最优数据压缩率

使用二叉树来表示前缀码：其叶结点为给定的字符。字符的二进制码字用从根结点到该字符叶结点的简单路径表示。其中 0 意味着“转向左孩子”，1 意味着“转向右孩子”：

文件的最优编码方案总是对应一棵满二叉树，即每个非叶结点都有两个孩子结点
若$C$为字母表且所有字符的出现频率为正数，则最优前缀码对应的树恰好有$|C|$个叶结点，每个叶结点对应字母表中的一个字符，且恰有$|C|-1$个内部结点

给定一棵对应前缀码的树$T$。对于字母表$C$中的每个字符$c$，令属性$c.freq$表示$c$在文件中出现的频率，令$d_T(c)$表示$c$的叶结点在树中的深度。则编码文件需要：

$$B(T)=\sum_{c \in C} c.freq \cdot d_T(c)$$

个二进制位，我们将$B(T)$定义为$T$的代价

构造霍夫曼编码

假定$C$是一个$n$个字符的集合，而其中每个字符$c \in C$都是一个对象，其属性$c.freq$给出了字符的出现频率。算法使用了一个以属性$freq$为关键字最小优先队列$Q$：

HUFFMAN(C)
n = |C|
Q = C
for i = 1 to n-1
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q)
    z.right = y = EXTRACT-MIN(Q)
    z.freq = x.freq + y.freq
    INSERT(Q, z)
return EXTRACT-MIN(Q)

假定$Q$是使用最小二叉堆实现，HUFFMAN 时间复杂度$O(nlgn)$
如果将最小二叉堆换为 van Emde Boas 树，时间复杂度$O(nlglgn)$

摊还分析

聚合分析

这种方法用来确定一个$n$个操作的序列的总代价的上界$T(n)$。因而每个操作的平均代价为$T(n)/n$。我们将平均代价作为每个操作的摊还代价，因此所有操作具有相同的摊还代价

栈操作

考虑由$n$个 PUSH、POP 和 MULTIPOP 组成的操作序列在一个空栈上的执行情况。其代价至多为$O(n)$，一个操作的平均时间为$O(n)/n=O(1)$。所以，所有三种栈操作的摊还代价都是$O(1)$

二进制计数器递增

我们用一个位数组$A[0..k-1]$作为计数器，其中$A.length = k$。当计数器中保存的二进制值为$x$时，$x$的最低位保存在$A[0]$中，而最高位保存在$A[k-1]$中。初始时$x=0$，因此对所有$i=0,1,..,k-1$，$A[i]=0$。为了将1（模$2^k$）加到计数器的值上，我们使用如下过程：

INCEREMENT(A)
i = 0
while i < A.length and A[i] == 1
    A[i] = 0
    i = i + 1
if i < A.length
    A[i] = 1

一般地，对一个初值为0的计数器，在执行一个由$n$个 INCEREMENT 操作组成的序列的过程中，$A[i]$会翻转$\lfloor n/2^i \rfloor$次。总翻转次数为：

$$\sum^{k-1}_{i=0}\lfloor \frac{n}{2^i} \rfloor < n \sum^{\infty}_{i=0}\frac{1}{2^i}=2n$$

因此，对一个初值为0的计数器，执行一个$n$个 INCEREMENT 操作的序列的最坏情况时间为$O(n)$。每个操作的平均代价，即摊还代价为$O(n)/n=O(1)$

核算法

用核算法进行摊还分析时，我们对不同操作赋予不同费用，赋予某些造成的费用可能多于或少于其实际代价。我们将赋予一个操作的费用称为它的摊还代价
当一个操作的摊还代价超出其实际代价时，我们将差额存入数据结构中的特定对象，存入的差额称为信用
对于后续操作中摊还代价小于实际代价的情况，信用可以用来支付差额

如果用$c_i$表示第$i$个操作的真实代价，用$\hat{c_i}$表示其摊还代价，则对任意$n$个操作的序列，要求：

$$\sum^n_{i=1} \hat{c_i} \geq \sum^n_{i=1}c_i$$

即数据结构所关联的信用必须一直为非负值

栈操作

为操作赋予如下摊还代价：

操作	代价
PUSH	2
POP	0
MULTIPOP	0

用1美元支付压栈操作的实际代价，将剩余1美元存为信用，用来支付将来出栈操作的代价
由于栈中的每个元素都存有1美元的信用，而栈中的元素始终是非负的，因此可以保证总信用值是非负的
因此，对任意$n$个 PUSH、POP 和 MULTIPOP 操作组成的序列，总摊还代价为总实际代价的上界由于总摊还代价为$O(n)$，总实际代价也是$O(n)$

二进制计数器递增

为操作赋予如下摊还代价：

操作	代价
一次置位操作	2

当进行置位时，用1美元支付置为操作的实际代价，另1美元存为信用，用来支付将来复位操作的代价
由于每位都存有1美元的信用，而计数器中1的个数始终是非负的，因此可以保证总信用值是非负的
因此，对任意$n$个 INCREMENT 操作，总摊还代价为总实际代价的上界。由于总摊还代价为$O(n)$，总实际代价也是$O(n)$

势能法

我们将对一个初始数据结构$D_0$执行$n$个操作。对每个$i=1,2,...,n$，令$c_i$为第$i$个操作的实际代价，令$D_i$为在数据结构$D_{i-1}$上执行第$i$个操作得到的结果数据结构。势函数$\Phi$将每个数据结构$D_i$映射到一个实数$\Phi(D_i)$，此值即为关联到数据结构$D_i$的势。第$i$个操作的摊还代价$\hat{c_i}$用势函数$\Phi$定义为：

$$\hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})$$

$n$个操作的总摊还代价为：

$$\sum^n_{i=1} \hat{c_i} = \sum^n_{i=1}(c_i+\Phi(D_i)-\Phi(D_{i-1}))=\sum^n_{i=1}c_i+\Phi(D_n)-\Phi(D_0)$$

如果能定义一个势函数$\Phi$，使得$\Phi(D_n) \geq \Phi(D_0)$，则总摊还代价$\sum^n_{i=1} \hat{c_i}$给出了总实际代价$\sum^n_{i=1}{c_i}$的一个上界

我们通常将$\Phi(D_0)$简单定义为0，然后说明对所有$i$，有$\Phi(D_i) \geq 0$

栈操作

对于初始的空栈$D_0$，有$\Phi(D_0)=0$。由于栈中对象数目永远不可能为负，所以第$i$步操作得到的栈$D_i$具有非负的势，即：

$$\Phi(D_i) \geq 0 = \Phi(D_0)$$

如果第$i$个操作是 PUSH 操作，此时栈中包含$s$个对象，则势差为：

$$\Phi(D_i)-\Phi(D_{i-1}) = (s+1)-s = 1$$

PUSH 摊还代价为：

$$\hat{c_i} = c_i+\Phi(D_i)-\Phi(D_{i-1}) = 1+1=2$$

如果第$i$个操作是 MULTIPOP 操作，将$k'=min(k,s)$个对象弹出栈，则势差为：

$$\Phi(D_i)-\Phi(D_{i-1}) =-k'$$

MULTIPOP 摊还代价为：

$$\hat{c_i} = c_i+\Phi(D_i)-\Phi(D_{i-1}) = k'-k'=0$$

如果第$i$个操作是 POP 操作，此时栈中包含$s$个对象，则势差为：

$$\Phi(D_i)-\Phi(D_{i-1}) = (s-1)-s = -1$$

POP 摊还代价为：

$$\hat{c_i} = c_i+\Phi(D_i)-\Phi(D_{i-1}) = 1-1=0$$

每个操作的摊还代价都是$O(1)$，因此，$n$个操作的总摊还代价为$O(n)$，为总实际代价的上界，所以$n$个操作的最坏情况时间为$O(n)$

二进制计数器递增

将计数器执行$i$次 INCREMENT 操作后的势定义为$b_i$：$i$次操作后计数器中1的个数
假设第$i$个 INCREMENT 操作将$t_i$个位复位，则其实际代价至多为$t_i+1$。势差为：

$$\Phi(D_i)-\Phi(D_{i-1}) \leq (b_{i-1}-t_i+1)-b_{i-1}=1-t_i$$

摊还代价为：

$$\hat{c_i} = c_i+\Phi(D_i)-\Phi(D_{i-1}) \leq (t_i+1)+(1-t_i)=2$$

如果计数器从0开始，则$\Phi(D_0)=0$。由于对所有$i$均有$\Phi(D_i)\geq 0$，因此，一个$n$个 INCREMENT 操作的序列的总摊还代价是总实际代价的上界，最坏情况时间为$O(n)$

动态表

表扩张

TABLE-INSERT(T, x)
if T.size == 0
    allocate T.table with 1 slot
    T.size = 1
if T.num == T.size
    allocate newtable with 2*T.size slots
    insert all items in T.table into newtable
    free T.table
    T.table = newtable
    T.size = 2 * T.size
insert x into T.table
T.num = T.num + 1

第$i$个操作的代价为：

$$c_i = \begin{cases} i \qquad & i-1 = 2^k \\ 1 \qquad & other \end{cases}$$

$n$个 TABLE-INSERT 操作的总代价为：

$$\sum^n_{i=1}c_i \leq n+\sum^{\lfloor lgn \rfloor}_{j=0}2^j<n+2n=3n$$

图算法

基本的图算法

图的表示

邻接链表

对于图$G=(V,E)$来说，其邻接链表表示由一个包含$|V|$条链表的数组$Adj$所构成，每个结点有一条链表
对于每个结点$u \in V$，邻接链表$Adj[u]$包含所有与结点$u$之间有边相连的结点$v$

• 如果$G$是一个有向图，则对于边$(u,v)$来说，结点$v$将出现在链表$Adj[u]$里，因此，所有邻接链表的长度之和等于$|E|$
• 如果$G$是一个无向图，则对于边$(u,v)$来说，结点$v$将出现在链表$Adj[u]$里，结点$u$将出现在链表$Adj[v]$里，因此，所有邻接链表的长度之和等于$2|E|$
• 不论是有向图还是无向图，邻接链表存储空间需求均为$\Theta(V+E)$

对邻接链表稍加修改，就可以用来表示权重图：只需要将边$(u,v)$的权重值$w(u,v)$存放放在结点$u$的邻接链表里
邻接链表的一个潜在缺陷是无法快速判断一条边$(u,v)$是否是图中的一条边

邻接矩阵

图$G$的邻接矩阵表示由一个$|V| \times |V|$的矩阵$A=(a_{ij})$予以表示，该矩阵满足下述条件：

$$a_{ij} = \begin{cases} 1 \qquad & (i,j) \in E \\ 0 \qquad & other \end{cases}$$

不管一个图有多少条边，邻接矩阵的空间需求均为$\Theta(V^2)$
邻接矩阵也可以用来表示权重图：直接将边$(u,v) \in E$的权重$w(u,v)$存放在邻接矩阵中的第$u$行第$v$列记录上

广度优先搜索（BFS）

为了跟踪算法的进展，广度优先搜索在概念上将每个结点涂上白色、灰色或黑色。所有结点在一开始的时候均涂上白色。在算法的推进过程中，这些结点可能会变成灰色或黑色
如果边$(u,v) \in E$且结点$u$是黑色，则结点$v$既可能是灰色也可能是黑色。也就是说，所有与黑色结点邻接的结点都以被发现。对于灰色结点来说，其邻接结点中可能存在未被发现的白色结点
在执行广度优先搜索的过程中将构造出一棵广度优先树

假定输入图$G=(V,E)$是以邻接链表所表示的：

BFS(G, s)
for each vertex u in G.V - {s}
    u.color = WHITE
    u.d = ∞
    u.π = NIL
s.color = GRAY
s.d = 0
s.π = NIL
Q = ∅
ENQUEUE(Q, s)
while Q != ∅
    u = DEQUEUE(Q)
    for each v in G.Adj[u]
        if v.color == WHITE
            v.color = GRAY
            v.d = u.d + 1
            v.π = u
            ENQUEUE(Q, v)
    u.color = BLACK

分析

广度优先搜索的总运行时间为$O(V+E)$

最短路径

我们定义从源结点$s$到结点$v$的最短路径距离$\delta(s,v)$为从结点$s$到结点$v$之间所有路径里面最少的边数
如果从结点$s$到结点$v$之间没有路径，则$\delta(s,v) = \infty$
我们称从结点$s$到结点$v$的长度为$\delta(s,v)$的路径为$s$到$v$的最短路径

设$G=(V,E)$为一个有向图或无向图，又假设 BFS 以$s$为源结点在图$G$上运行。那么在算法执行过程中，BFS 将发现从源结点$s$可以到达的所有结点$v \in V$，并在算法终止时，对于所有的$v \in V,v.d = \delta(s,v)$。而且，对于任意可以从$s$到达的结点$v \neq s$，从源结点$s$到结点$v$的其中一条最短路径为从结点$s$到结点$v.\pi$的最短路径再加上边$(v.\pi,v)$

广度优先树

我们定义图$G$的前驱子图为$G_\pi =(V_\pi,E_\pi)$，其中$V_\pi = \{v\in V:v.\pi \neq NIL\} \cup \{s\}$，$E_\pi = \{(v.\pi,v):v \in V_\pi - \{s\}\}$
当运行在一个有向或无向图$G=(V,E)$上时，BFS 过程所建造出来的$\pi$属性使得前驱子图$G_\pi=(V_\pi,E_\pi)$成为一棵广度优先树

PRINT-PATH 可打印出从源结点$s$到结点$v$的一条最短路径上的所有结点，这里假定 BFS 已经计算出一棵广度优先树：

PRINT-PATH(G, s, v)
if v == s
    print s
elseif v.π == NIL
    print "no path from" s "to" v "exists"
else
    PRINT-PATH(G, s, v.π)
    print v

深度优先搜索（DFS）

我们定义图$G$的前驱子图为$G_\pi =(V,E_\pi)$，其中$E_\pi = \{(v.\pi,v):v \in V \land v.\pi \neq NIL\}$
与广度优先搜索不同，深度优先搜索的前驱子图可能由多颗树组成，因为搜索可能从多个源结点重复进行
深度优先搜索的前驱子图形成一个由多颗深度优先树构成的深度优先森林，森林$E_\pi$中的边仍然称为树边

像广度优先搜索一样，深度优先搜索算法在搜索过程中也是对结点进行涂色来指明结点的状态。每个结点的初始颜色都是白色，在结点被发现后变为灰色，在其邻接链表被扫描完成后变为黑色。该方法可以保证每个结点仅在一棵深度优先树中出现，因此，所有的深度优先树是不相交的

深度优先算法在每个结点盖上一个时间戳。每个结点$v$有两个时间戳：第一个时间戳$v.d$记录结点$v$第一次被发现的时间（涂上灰色的时候），第二个时间戳$v.f$记录的是搜索完成对$v$的邻接链表扫描的时间（涂上黑色的时候）

输入图$G$既可以是无向图，可以是有向图。变量$time$是一个全局变量，用来计算时间戳：

DFS(G)
for each vertex u in G.V
    u.color = WHITE
    u.π = NIL
time = 0
for each vertex u in G.V
    if u.color == WHITE
        DFS-VISIT(G, u)

DFS-VISIT(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each v in G.Adj[u]
    if v.color == WHITE
        v.π = u
        DFS-VISIT(G, v)
u.color = BLACK
time = time + 1
u.f = time

分析

深度优先搜索的总运行时间为$O(V+E)$

深度优先搜索的性质

括号化定理：在对有向或无向图$G=(V,E)$进行的任意深度优先搜索中，对于任意两个结点$u$和$v$来说，下面三种情况只有一成立：

• 区间$[u.d,u.f]$和区间$[v.d,v.f]$完全分离，在深度优先森林中，结点$u$不是结点$v$的后代，结点$v$也不是结点$u$的后代
• 区间$[u.d,u.f]$完全包含在区间$[v.d,v.f]$内，在深度优先树中，结点$u$是结点$v$的后代
• 区间$[v.d,v.f]$完全包含在区间$[u.d,u.f]$内，在深度优先树中，结点$v$是结点$u$的后代

后代区间的嵌套：在有向或无向图$G$的深度优先森林中，结点$v$是结点$u$的真后代当且仅当$u.d<v.d<v.f<u.f$成立
白色路径定理：在有向或无向图$G=(V,E)$的深度优先森林中，结点$v$是结点$u$的后代当且仅当在发现结点$u$的时间$u.d$，存在一条从结点$u$到结点$v$的全部由白色结点所构成的路径

边的分类

• 树边：为深度优先森林$G_\pi$中的边，如果结点$v$是因算法对边$(u,v)$的探索而首先被发现，则$(u,v)$是一条树边
• 后向边：后向边$(u,v)$是将结点$u$连接到其在深度优先树中（一个）祖先结点$v$的边。由于有向图中可以有自循环，自循环也被认为是后向边
• 前向边：是将结点$u$连接到其在深度优先树中一个后代结点$v$的边$(u,v)$
• 横向边：指其他所有的边。这些边可以连接同一棵深度优先树中的结点，只要其中一个结点不是另外一个结点的祖先，也可以连接不同深度优先树中的两个结点

结点$v$的颜色能够告诉我们关于该条边的一些信息：

• 结点$v$为白色表明该条边$(u,v)$是一条树边
• 结点$v$为灰色表明该条边$(u,v)$是一条后向边
• 结点$v$为黑色表明该条边$(u,v)$是一条前向边或横向边

在对无向图$G$进行深度优先搜索时，每条边要么是树边，要么是后向边

拓扑排序

对于一个有向无环图$G=(V,E)$来说，其拓扑排序是$G$中所有结点的一种线性次序，该次序满足如下条件：
如果图$G$包含边$(u,v)$，则结点$u$在拓扑排序中处于结点$v$的前面（如果图$G$包含环路，则不可能排出一个线性次序）

下面的简单算法可以对一个有向无环图进行拓扑排序，完成时间$\Theta(V+E)$：

TOPOLOGICAL-SORT(G)
call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return the linked list of vertices

强连通分量

有向图$G=(V,E)$的强连通分量是一个最大结点集合$C \subseteq V$，对于该集合中的任意一对结点$u$和$v$来说，路径$u \leadsto v$和路径$v \leadsto u$同时存在

下面的 Kosaraju 算法使用两次深度优先搜索来计算有向图$G-=(V,E)$的强连通分量，时间复杂度$\Theta(V+E)$：

STRONGLY-CONNECTED-COMPONENTS(G)
call DFS(G) to compute finishing times u.f for each vertex u
compute G^T
call DFS(G^T), but in the main loop of DFS, consider the vertices
    in order of decreasing u.f (as computed in line 1)
output the vertices of each tree in the depth-first forest formed in line 3 as a 
    separate strongly connected component

最小生成树

最小生成树的形成

假定有一个连通无向图$G=(V,E)$和权重函数$w:E\rightarrow \Reals$。我们希望找出图$G$的一棵最小生成树

使用贪心策略来生成最小生成树：

GENERIC-MST(G, w)
A = ∅
while A does not form a spanning tree
    find an edge(u,v) that is safe for A
    A = A ∪ {(u,v)}
return A

Kruskal算法

Kruskal 算法使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树。通过测试 FIND-SET(u) 是否等于 FIND-SET(v) 来判断结点$u$和结点$v$是否属于同一棵树，使用 UNION 过程来对两棵树进行合并
时间复杂度$O(ElgV)$：

MST-KRUSKAL(G, w)
A = ∅
for each vertex v in G.V
    MAKE-SET(v)
sort the edges of G.E into nondecreasing order by weight w
for each edge(u,v) in G.E, taken in nondecreasing order by weight
    if FIND-SET(u) != FIND-SET(v)
        A = A ∪ {(u,v)}
        UNION(u,v)
return A

Prim算法

Prim 算法每一步在连接集合$A$和$A$之外的结点的所有边中，选择一条轻量级边加入到$A$中

连通图$G$和最小生成树的根结点$r$将作为算法的输入。在算法的执行过程中，所有不在树$A$中的结点都存放在一个基于$key$属性的最小优先队列$Q$中。对每个结点$v$，属性$v.key$保存的是连接$v$和树中结点的所有边中最小边的权重。属性$v.\pi$给出的是结点$v$在树中的父结点

若使用二叉最小优先队列，时间复杂度$O(VlgV+ElgV)=O(ElgV)$；若使用斐波那契堆来实现最小优先队列，时间复杂度$O(E+VlgV)$：

MST-PRIM(G, w, r)
for each u in G.V
    u.key = ∞
    u.π = NIL
r.key = 0
Q = G.V
while Q != ∅
    u = EXTRACT-MIN(Q)
    for each v in G.Adj[u]
    if v in Q and w(u,v)  < v.key
        v.π = u
        v.key = w(u,v)

单源最短路径

在最短路径问题中，我们给定一个带权重的有向图$G=(V,E)$和权重函数$w: E\rightarrow \Reals$，该权重函数将每条边映射到实数值的权重上
图中一条路径$p=\langle v_0,v_1,...,b_k \rangle$的权重$w(p)$是构成该路径的所有边的权重之和：

$$w(p)=\sum^k_{i=1}w(v_{i-1},v_i)$$

定义从结点a$u$到结点$v$的最短路径权重$\delta(u,v)$如下：

$$\delta(u,v)\leq \begin{cases} min\{w(p):u \leadsto^p v \} \qquad & if \ exists \ a\ path\ from\ u \ to \ v \\ \infty \qquad & other \end{cases}$$

从结点$u$到结点$v$的最短路径定义为任何一条权重为$w(p)=\delta(w,v)$的从$u$到$v$的路径$p$

常规概念

负权重的边

如果图$G=(V,E)$不包含从源结点$s$可以到达的权重为负值的环路，则对于所有的结点$v \in V$，最短路径权重$\delta(s,v)$都有精确定义，即使其取值为负数
如果图$G$包含从$s$可以达到的权重为负值的环路，则最短路径权重无定义

环路

最短路径不能包含权重为负值的环路
最短路径不能包含权重为正值的环路

最短路径的表示

$\pi$值所诱导的前驱子图$G_\pi=(V_\pi,E_\pi)$定义如下：

$$V_\pi = \{v\in V:v.\pi \neq NIL\} \cup \{s\}$$

$$E_\pi = \{(v.\pi,v) \in E:v \in V_\pi - \{s\}\}$$

在算法终止时，$G_\pi$是一棵最短路径树
最短路径不一定是唯一的，最短路径树也不一定是唯一的

松弛操作

对于每个结点$v$，我们维持一个属性$v.d$来记录从原结点$s$到结点$v$的最短路径权重的上界。我们称$v.d$为$s$到$v$的最短路径估计。我们使用下面运行时间为$\Theta(V)$的算法来对最短路径估计和前驱结点进行初始化：

INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v in G.V
    v.d = ∞
    v.π = NIL
s.d = 0

RELAX 过程对边$(u,v)$在$O(1)$时间内进行松弛操作：

RELAX(u, v, w)
if v.d > u.d + w(u,v)
    v.d = u.d + w(u,v)
    v.π = u

最短路径和松弛操作的性质

三角不等式性质：对于任何边$(u,v) \in E$，有$\delta(s,v) \leq \delta(s,u)+w(u,v)$
上界性质：对于所有的结点$v \in V$，有$v.d \geq \delta(s,v)$。一旦$v.d$的取值达到$\delta(s,v)$，其值将不再发生变化
非路径性质：如果从结点$s$到结点$v$之间不存在路径，则有$v.d=\delta(s,v)=\infty$
收敛性质：对于某些结点$u,v \in V$，如果$s \leadsto u \rightarrow v$是图$G$中的一条最短路径，并且在对边$(u,v)$进行松弛前的任意时间有$u.d=\delta(s,u)$，则在之后的所有时间有$v.d=\delta(s,v)$
路径松弛性质：如果$p=\langle v_0,v_1,...,v_k \rangle$是从源结点$s=v_0$到结点$v_k$的一条最短路径，且对$p$中的边所进行的松弛的次序为$(v_0,v_1)$，$(v_1,v_2)$，…，$(v_{k-1},v_k)$，则$v_k.d=\delta(s,v_k)$，该性质的成立与任何其他的松弛操作无关，即使这些松弛操作是与对$p$上的边所进行的松弛操作是穿插进行的

Bellman-Ford算法

Bellman-Ford 算法解决一般情况下的单元最短路径问题，边的权重可以为负值
Bellman-Ford 算法返回 TRUE 值当且仅当输入图不包含可以从源结点到达的权重为负值的环路：

BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i = 1 to |G.V| - 1
    for each edge(u,v) in G.E
        RELAX(u, v, w)
for each edge(u,v) in G.E
    if v.d > u.d + w(u,v)
        return FALSE
return TRUE

Bellman-Ford 算法总运行时间$O(VE)$

有向无环图中的单源最短路径问题

根据结点的拓扑排序次序来对带权重的有向无环图$G=(V,E)$进行边的松弛操作，我们便可以在$O(V,E)$时间内计算出从单个源结点到所有结点之间的最短路径：

DAG-SHORTEST-PATHS(G, w, s)
topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex u, taken in topologically sorted order
    for each vertex v in G.Adj[u]
    RELAX(u, v, w)

Dijkstra算法

Dijkstra 算法要求所有边的权重都为非负值：

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = ∅
Q = G.V
while Q != ∅
    u = EXTRACT-MIN(Q)
    S = S ∪ {u}
    for each vertex v in G.Adj[u]
        RELAX(u, v, w)

Dijkstra 算法总运行时间依赖于最小优先队列的实现：

• 通过利用结点的编号为$1 - |V|$来维持最小优先队列。在这种情况下，每次 INSERT 和 DECREASE-KEY 操作的执行时间为$O(1)$，每次 EXTRACT-MIN 的操作时间为$O(V)$，算法总运行时间为$O(V^2+E)=O(V^2)$
• 若图为稀疏图，特别地，如果$E=o(V^2/lgV)$，则可以通过二叉堆来实现最小优先队列，每次 EXTRACT-MIN 的操作时间为$O(lgV)$，每次 DECREASE-KEY 的操作时间为$O(lgV)$，构建最小二叉堆的成本为$O(V)$，算法总运行时间为$O((V+E)lgV)$。若所有结点都可以从源结点到达，则该时间为$O(ElgV)$
• 若使用斐波那契堆来时间最小优先队列，每次 EXTRACT-MIN 的操作时间为$O(lgV)$，每次 DECREASE-KEY 的操作时间为$O(1)$，算法总运行时间为$O(VlgV+E)$

差分约束和最短路径

差分约束系统

设向量$x=(x_1,x_2,...,x_n)$为差分约束系统$Ax \leq b$的一个解，设$d$为任意常数，则$x+d=(x_1+d,x_2+d,...,x_n+d)$也是该差分约束系统的一个解

约束图

给定差分约束系统$Ax \leq b$，其对应的约束图是一个带权重的有向图$G=(V,E)$，这里：

$$V=\{v_0,v_1,...,v_n\}$$

$$E=\{(v_i,v_j):v_j-v_i \leq b_k\text{是一个约束条件}\} \cup \{(v_0,v_1),(v_0,v_2),...(v_0,v_n)\}$$

• 约束图包含一个额外的结点$v_0$，用来保证图中至少存在一个结点，从其出发可以到达所以其他的结点
• 如果$x_j-x_i \leq b_k$是一个差分约束条件，则边$(v_i,v_j)$的权重为$w(v_i,v_j)=b_k$
• 所有从结点$v_0$发出的边的权重为0

给定差分约束系统$Ax \leq b$，设$G=(V,E)$是该差分约束系统所对应的约束图。如果图$G$不包含权重为负值的环路，则：

$$x=(\delta(v_0,v_1),\delta(v_0,v_2),...,\delta(v_0,v_n))$$

是该系统的一个可行解。如果图$G$包含权重为负值的环路，则该系统没有可行解

求解差分约束系统

一个有$n$个未知变量和$m$个约束条件的差分约束系统所生成的约束图有$n+1$个结点和$m+n$条边。使用 Bellman-Ford 算法可以在$O((n+1)(m+n)) = O(n^2+mn)$时间内求解该系统

所有结点对的最短路径

假定结点的编号为$1,2,...,|V|$，因此，算法的输入将是一个$n \times n$的矩阵$W$，该矩阵代表的是一个有$n$个结点的有向图$G=(V,E)$的边的权重，即$W=(w_{ij})$，其中：

$$w_{ij} = \begin{cases} 0 \qquad & i=j \\ w_{ij} \qquad & i \neq j \land (i,j) \in E \\ \infty \qquad & i \neq j \land (i,j) \notin E \end{cases}$$

我们允许存在负权重的边，但假定图中不包括权重为负值的环路

所有结点对最短路径算法的表格输出也是一个$n \times n$的矩阵$D=(d_{ij})$，其中$d_{ij}$代表的是从结点$i$到结点$j$的一条最短路径的权重
前驱结点矩阵$\Pi =(\pi_{ij})$，其中$\pi_{ij}$在$i=j$或从$i$到$j$不存在路径时为$NIL$，在其他情况下给出的是从结点$i$到结点$j$的某条最短路径上结点$j$的前驱结点。由矩阵$\Pi$的第$i$行所诱导的子图一个是一棵根结点为$i$的最短路径树。对于每个结点$i \in V$，定义图$G$对于结点$i$的前驱子图为$G_{\pi,i}=(V_{\pi,i},E_{\pi,i})$，其中：

$$V_{\pi,i}=\{j\in V:\pi_{ij} \neq NIL\} \cup \{i\} \qquad E_{\pi,i}=\{(\pi_{ij},j):j\in V_{\pi,i}-\{i\}\}$$

如果$G_{\pi,i}$是一棵最短路径树，则下面的过程将打印出从结点$i$到结点$j$的一条最短路径：

PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
if i == j
    print i
elseif π_{ij} == NIL
    print "no path from" i "to" j "exists"
else
    PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, π_{ij})
    print j

最短路径和矩阵乘法

最短路径的结构

考虑从结点$i$到结点$j$的一条最短路径$p$，假定$p$至多包含$m$条边，还假定没有权重为负值的环路，且$m$为有限值。如果$i=j$，则$p$的权重为0且不包含任何边。如果结点$i$和结点$j$不同，则将路径分解为$i \leadsto^{p'}k \rightarrow j$，其中路径$p'$至多包含$m-1$条边，则有：

$$\delta(i,j)=\delta(i,k)+w_{kj}$$

所有结点对最短路径问题的递归解

设$l^{(m)}_{ij}$为从结点$i$到结点$j$的至多包含$m$条边的任意路径中的最小权重。当$m=0$时，从结点$i$到结点$j$之间存在一条没有边的最短路径当且仅当$i=j$，因此有：

$$l^{(m)}_{ij} = \begin{cases} 0 \qquad & i=j \\ \infty \qquad & i \neq j \end{cases}$$

递归定义：

$$l^{(m)}_{ij} = min\{l^{(m-1)}_{ij},min_{1 \leq k \leq n}\{l^{(m-1)}_{ij} +w_{kj}\}\} = min_{1 \leq k \leq n}\{l^{(m-1)}_{ij} + w_{kj}\}$$

最短路径权重可以由下面的公式给出：

$$\delta(i,j)=l^{(n-1)}_{ij}=l^{(n)}_{ij}=l^{(n+1)}_{ij} = ...$$

自底向上计算最短路径权重

EXTEND-SHORTEST-PATHS 过程可以在给定$w$和$L^{(m-1)}$的情况下，计算出$L^{(m)}$，算法运行时间$\Theta(n^3)$：

EXTEND-SHORTEST-PATHS(L, W)
n = L.rows
let L' = (l'_{ij}) be a new n * n matrix
for i = 1 to n
    for j = 1 to n
        l'_{ij} = ∞
        for k = 1 to n
            l'_{ij} = min(l'_{ij}, l_{ik} + w_{kj})
return L'

设$A \cdot B$表示由算法 EXTEND-SHORTEST-PATHS(A, B) 所返回的矩阵“乘积”，我们可以计算出下面由$n-1$个矩阵所构成的矩阵序列：
$L^{(1)} = L^{(0)} \cdot W = W$
$L^{(2)} = L^{(1)} \cdot W = W^2$
$L^{(3)} = L^{(2)} \cdot W = W^3$
…
$L^{(n-1)} = L^{(n-2)} \cdot W = W^{n-1}$

SLOW-ALL-PAIRS-SHORTEST-PATHS 过程可以在$\Theta(n^4)$的时间内计算出矩阵$L^{(n-1)} = W^{n-1}$：

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L(1) = W
for m = 2 to n-1
    let L(m) be a new n * n matrix
    L(m) = EXTEND-SHORTEST-PATHS(L(m-1), W)
return L(n-1)

可以仅用$\lceil lg(n-1) \rceil$个矩阵乘积来计算矩阵$L^{(n-1)}$：
$L^{(1)} = W$
$L^{(2)} = W^2 = W \cdot W$
$L^{(4)} = W^4 = W^2 \cdot W^2$
$L^{(8)} = W^8 = W^4 \cdot W^4$
…
$L^{(2^{\lceil lg(n-1) \rceil})} = W^{2^{\lceil lg(n-1) \rceil}} = W^{2^{\lceil lg(n-1) \rceil-1}} \cdot W^{2^{\lceil lg(n-1) \rceil-1}}$
由于$2^{\lceil lg(n-1) \rceil}\geq n-1$，最后有$L^{(2^{\lceil lg(n-1) \rceil})}=L^{(n-1)}$
FASTER-ALL-PAIRS-SHORTEST-PATHS 过程使用重复平方技术来计算上述矩阵序列，运行时间为$\Theta(n^3lgn)$：

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
n = W.rows
L(1) = W
m = 1
while m < n-1
    let L(2m) be a new n * n matrix
    L(2m) = EXTEND-SHORTEST-PATHS(L(m), L(m))
return L(m)

Floyd-Warshall算法

所有结点对最短路径问题的一个递归解

设$d^{(k)}_{ij}$为从结点$i$到结点$j$的所有中间结点全部取自集合$\{1,2,...,k\}$的一条最短路径的权重。递归定义$d^{(k)}_{ij}$如下：

$$d^{(k)}_{ij} = \begin{cases} w_{ij} \qquad & k=0 \\ min(d^{(k-1)}_{ij},d^{(k-1)}_{ik}+d^{(k-1)}_{kj}) \qquad & k \geq 1 \end{cases}$$

矩阵$D^{(n)} = (d^{(n)}_{ij})$给出的就是最后的答案：对于所有的$i,j \in V$，$d^{(n)}_{ij}=\delta(i,j)$

自底向上计算最短路径权重

FLOYD-WARSHALL 算法的输入为一个$n \times n$的矩阵$W$，返回最短路径权重矩阵$D^{(n)}$，运行时间为$\Theta(V^3)$：

FLOYD-WARSHALL(W)
n = W.rows
D(0) = W
for k = 1 to n
    let D(k) = (d(k)_{ij}) be a new n * n matrix
    for i = 1 to n
        for j = 1 to n
            d(k)_{ij} = min(d(k-1)_{ij},d(k-1)_{ik}+d(k-1)_{kj})
return D(n)

构建一条最短路径

在 Floyd-Warshall 算法中，有多种不同的方法来构建最短路径

• 先计算最短路径权重矩阵$D$，然后从$D$矩阵来构造前驱矩阵$\Pi$
• 可以在计算矩阵$D^{(k)}$的同时计算前驱矩阵$\Pi$。即计算一个矩阵序列$\Pi^{(0)}$，$\Pi^{(1)}$，…，$\Pi^{(n)}$。定义$\pi^{(k)}_{ij}$为从结点$i$到结点$j$的一条所有中间结点都取自集合$\{1,2,...,k\}$的最短路径上$j$的前驱结点

当$k=0$时，从$i$到$j$的一条最短路径没有中间结点，因此：

$$\pi^{(0)}_{ij} = \begin{cases} NIL \qquad & i=j \lor w_{ij} = \infty \\ i \qquad & i \neq j \land w_{ij} < \infty \end{cases}$$

对于$k \geq 1$，如果考虑路径$i \leadsto k \leadsto j,k \neq j$，则所选择的结点$j$的前驱与我们选择的从结点$k$到结点$j$的一条中间结点全部取自集合$\{1,2,...,k-1\}$的最短路径上的前驱是一样的。否则，所选择的结点$j$的前驱与选择的从结点$i$到结点$j$的一条中间结点全部取自集合$\{1,2,...,k-1\}$的最短路径上的前驱是一样的。也就是说，对于$k \geq 1$，有：

$$\pi^{(k)}_{ij} = \begin{cases} \pi^{(k-1)}_{ij} \qquad & d^{(k-1)}_{ij} \leq d^{(k-1)}_{ik}+d^{(k-1)}_{kj} \\ \pi^{(k-1)}_{kj} \qquad & d^{(k-1)}_{ij} > d^{(k-1)}_{ik}+d^{(k-1)}_{kj} \end{cases}$$

有向图的传递闭包

定义图$G$的传递闭包为图$G^*=(V,E^*)$，其中$E^*=\{(i,j):\text{如果图}G\text{中包含一条从结点}i\text{到结点}j\text{的路径}\}$

一种时间复杂度为$\Theta(n^3)$的计算图$G$的传递闭包的办法是给$E$的每条边赋予权重1，然后运行 Floyd-Warshall 算法。如果存在一条从结点$i$到结点$j$的路径，则有$d_{ij}<n$；否则$d_{ij}=\infty$

另一种类似办法是：以逻辑或操作（$\lor$）和逻辑与操作（$\land$）来替换 Floyd-Warshall 算法中的算术操作 min 和 +，以此节省时间和空间

对于$i,j,k=1,2,...,n$，定义：如果图$G$中存在一条从结点$i$到结点$j$的所有中间结点都取自集合$\{1,2,...,k\}$的路径，则$t^{(k)}_{ij}$为1；否则，$t^{(k)}_{ij}$为0。递归定义如下：

$$t^{(0)}_{ij} = \begin{cases} 0 \qquad & i \neq j \land (i,j) \notin E \\ 1 \qquad & i = j \lor (i,j) \in E \end{cases}$$

对于$k \geq 1$：

$$t^{(k)}_{ij} = t^{(k-1)}_{ij} \lor (t^{(k-1)}_{ik} \land t^{(k-1)}_{kj})$$

TRANSITIVE-CLOSURE(G)
n = |G.V|
let T(0) = (t(0)_{ij}) be a new n * n matrix
for i = 1 to n
    for j = 1 to n
        if i == j or (i,j) in G.E
            t(0)_{ij} = 1
        else
            t(0)_{ij} = 0
for k = 1 to n
    let T(k) = (t(k)_{ij}) be a new n * n matrix
    for i = 1 to n
        for j = 1 to n
            t(k)_{ij} = t(k-1)_{ij} || (t(k-1)_{ik} && t(k-1)_{kj})
return T(n)

用于稀疏图的Johnson算法

Johnson 算法可以在$O(V^2lgV+VE)$时间内找到所有结点对之间的最短路径

Johnson 算法使用的技术称为重新赋予权重：
如果图$G=(V,E)$中所有的边权重$w$均为非负值，则可以通过对每一个结点运行一次 Dijkstra 算法来找到所有结点对之间的最短路径；如果使用斐波那契堆最小优先队列，该算法的运行时间$O(V^2lgV+VE)$
如果图$G=(V,E)$包含权重为负值的边，但没有权重为负值的环路，则只要计算出一组新的非负权重值，然后使用同样的方法。新赋予的权重$\hat{w}$必须满足以下两个重要性质：

• 对于所有结点对$u,v \in V$，一条路径$p$是在使用权重函数$w$时从结点$u$到结点$v$的一条最短路径，当且仅当$p$是在使用权重函数$\hat{w}$时从$u$到$v$的一条最短路径
• 对于所有的边$(u,v)$，新权重$\hat{w}(u,v)$为非负值

重新赋予权重来维持最短路径

给定带权重的有向图$G=(V,E)$，其权重函数为$w:E \rightarrow \Reals$，设$h:V \rightarrow \Reals$为任意函数，该函数将结点映射到实数上。对于每条边$(u,v) \in E$，定义：

$$\hat{w}(u,v)=w(u,v)+h(u)-h(v)$$

设$p=\langle v_0,v_1,...,v_k \rangle$为从结点$v_0$到结点$v_k$的任意一条理解，那么$p$是在使用权重函数$w$时从结点$v_0$到结点$v_k$的一条最短路径，当且仅当$p$是在使用权重函数$\hat{w}$时从结点$v_0$到结点$v_k$的一条最短路径，即$w(p)=\delta(v_0,v_k)$当且仅当$\hat{w}(p)=\hat{\delta}(v_0,v_k)$。而且，图$G$在使用权重函数$w$时不包含权重为负值的环路，当且仅当$p$在使用权重函数$\hat{w}$也不包括权重为负值的环路。

计算所有结点对之间的最短路径

Johnson 算法在执行过程中需要使用 Bellman-Ford 算法和 Dijkstra 算法作为子程序来计算所有结点对之间的最短路径。该算算假定所有的边都保持在邻接链表里，其返回一个$|V| \times |V|$的矩阵$D=d_{ij},d_{ij}=\delta(i,j)$，或者报告输入图包含一个权重为负值的环路：

JOHNSON(G, w)
compute G', where G'.V = G.V ∪ {s},
    G'.E = G.E ∪ {(s,v):v in G.V} 
    and w(s,v) = 0 for all v in G.V 
if BELLMAN-FOLD(G', w, s) == FALSE
    print "the input graph contains a negative-weight cycle"
else
    for each vertex v in G'.V
        set h(v) to the value of δ(s, v) computed by the Bellman-Ford algorithm
    for each edge(u, v) in G'.E
        \hat_w(u,v) = w(u,v) + h(u) - h(v)
    let D = (d_{uv}) be a new n * n matrix
    for each vertex u in G.V
        run DIJKSTRA(G, \hat_w, u) to compute \hat_δ(u, v) for all v in G.V
        for each vertex v in G.V
        d_{uv} = \hat_δ(u, v) + h(v) - h(u)
    return D

如果使用斐波那契堆来实现 Dijkstra 算法里的最小优先队列，则 Johnson 算法的运行时间为$O(V^2lgV+VE)$，使用更简单的二叉最小堆实现则运行时间为$O(VElgV)$

最大流

流网络

流网络和流

流网络$G=(V,E)$是一个有向图，图中每条边$(u,v) \in E$有一个非负的容量值$c(u,v) \geq 0$
如果边集合$E$包含一条边$(u,v)$，则图中不存在反方向的边$(v,u)$
在图中不允许自循环，对于每个结点$v \in V$，流网络都包含一条路径$s \leadsto v \leadsto t$
流网络图是连通的，且由于除源结点外的每个结点都至少有一条进入的边，有$|E| \geq |V|-1$

流的形式化定义：
设$G=(V,E)$为一个流网络，其容量函数为$c$。设$s$为网络的源结点，$t$为汇点。$G$中的流是一个实值函数$f$：$V \times V \rightarrow \Reals$，满足下面的两条性质：

• 容量限制：对于所有的结点$u，v \in V$，要求$0 \leq f(u,v) \leq c(u,v)$
• 流量守恒：对于所有的结点$u \in V- \{s,t\}$，要求：

$$\sum_{v\in V}f(u,v) = \sum_{v\in V}f(v,u)$$

当$(u,v) \notin E$时，从结点$u$到结点$v$之间没有流，因此$f(u,v)=0$

一个流$f$的值$|f|$定义如下：

$$|f|=\sum_{v \in V}f(s,v)-\sum_{v \in V}f(v,s)$$

Ford-Fulkerson方法

Ford-Fulkerson 方法循环增加流的值。在开始的时候，对于所有的结点$u,v \in V$，$f(u,v)=0$，给出的初始流值为0。在每次迭代中，我们将图$G$的流值进行增加，方法就是在一个关联的残存网络$G_f$中寻找一条增广路径。重复对流进行这一过程，直到残存网络中不再增加增广路径为止：

FORD-FULKERSON-METHOD(G, s, t)
initialize flow f to 0
while there exists an augmenting path p in the residual network Gf
    augment flow f along p
return f

残存网络

残存网络由那些仍有空间对流量进行调整的边构成。流网络的一条边可以允许的额外流量等于该边的容量减去该边上的流量：

• 如果该差值为正，则将该条边置于图$G_f$中，并将其残存容量设置为$c_f(u,v)=c(u,v)-f(u,v)$；同时将边$(v,u)$加入到图$G_f$中，并将其残存容量设置为$c_f(v,u)=f(u,v)$
• 如果边$(u,v)$的流量等于其容量，则其$c_f(u,v)=0$，该条边将不属于图$G_f$

形式化地，假定有一个流网络$G=(V,E)$，其源结点为$s$，汇点为$t$。设$f$为图$G$中的一个流，考虑结点对$u,v \in V$，定义残存容量$c_f(u,v)$：

$$c_f(u,v) = \begin{cases} c(u,v)-f(u,v) \qquad & (u,v) \in E\\ f(v,u) \qquad & (v,u) \in E\\ 0 \qquad & other \end{cases}$$

给定一个流网络$G=(V,E)$和一个流$f$，则由$f$所诱导的图$G$的残存网络为$G_f=(V,E_f)$，其中：

$$E_f = \{(u,v) \in V \times V:c_f(u,v)>0\}$$

如果$f$是$G$的一个流，$f'$是对应的残存网络$G_f$中的一个流，定义$f \uparrow f'$为流$f'$对流$f$的递增，它是一个从$V \times V \rightarrow \Reals$的函数，其定义如下：

$$(f \uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v)-f'(v,u) \qquad & (u,v) \in E\\ 0 \qquad & other \end{cases}$$

增广路径

给定流网络$G=(V,E)$和流$f$，增广路径$p$是残存网络$G_f$中一条从源结点$s$到汇点$t$的简单路径
我们称在一条增广路径$p$上能够为每条边增加的流量的最大值为路径$p$的残存容量，该容量由下面的表达式给出：

$$c_f(p)=min\{c_f(u,v):(u,v)\text{属于路径}p\}$$

流网络的切割

流网络$G=(V,E)$中的一个切割$(S,T)$将结点集合$V$划分为$S$和$T=V-S$两个集合，使得$s \in S$，$t \in T$。若$f$是一个流，则定义横跨切割$(S,T)$的净流量$f(S,T)$如下：

$$f(S,T)=\sum_{u\in S}\sum_{v \in T}f(u,v)-\sum_{u\in S}\sum_{v \in T}f(v,u)$$

切割$(S,T)$的容量：

$$c(S,T)=\sum_{u\in S}\sum_{v \in T}c(u,v)$$

一个网络的最小切割是整个网络中容量最小的切割

设$f$为流网络$G$的一个流，该流网络的源结点为$s$，汇点为$t$，设$(S,T)$为流网络$G$的任意切割，则横跨切割$(S,T)$的净流量为$f(S,T)=|f|$
流网络$G$中任意流$f$的值不能超过$G$的任意切割的容量
设$f$为流网络$G=(V,E)$中的一个流，该流网络的源结点为$s$，汇点为$t$，则下面的条件是等价的：

• $f$是$G$的一个最大流
• 残存网络$G_f$不包括任何增广路径
• $|f|=c(S,T)$，其中$(S,T)$是流网络$G$的某个切割

基本的Ford-Fulkerson算法

在 Ford-Fulkerson 方法的每次迭代中，寻找某条增广路径$p$，然后使用$p$来对流$f$进行修改（增加）。通过为每条边$(u,v) \in E$更新流属性$(u,v).f$来计算流网络$G=(V,E)$中的最大流：

FORD-FULKERSON(G, s, t)
for each edge(u,v) in G.E
    (u,v).f = 0
while there exists a path p from s to t in the residual network Gf
    cf(p) = min{cf(u,v):(u,v)is in p}
    for each edge(u,v) in p
        if (u,v) in E
            (u,v).f = (u,v).f + cf(p)
        else
            (u,v).f = (u,v).f - cf(p)

如果$f^*$表示转换后网络中的一个最大流，则 Ford-Fulkerson 算法的运行时间为$O(E|f^*|)$

Edmonds-Karp算法

通过在算法第3行寻找增广路径的操作中使用广度优先搜索来改善 Ford-Fulkerson 算法的效率：
在残存网络中选择的增广路径是一条从源结点$s$到汇点$t$的最短路径，其中每条边的权重为单位距离
Edmonds-Karp 算法的运行时间为$O(VE^2)$