跳到主要内容

分治法

2.1 乘法​

截止第二章 2.1，乘法可以被认为是一个 O(n2)O(n^2) 的算法。

2.2 递推式​

主定理 对于常数 a>0,b>1a>0, b>1 和 d>0d>0，若 T(n)=aT(⌈nb⌉)+O(nd)T(n)=aT\left( \left\lceil \frac{n}{b} \right\rceil \right)+O(n^d)，则

T(n)={O(nd),d>log⁡baO(ndlog⁡n),d=log⁡baO(nlog⁡ba),d<log⁡baT\left( n \right) =\left\{ \begin{aligned} O\left( n^d \right) , d&>\log _ba\\ O\left( n^d\log n \right) , d&=\log _ba\\ O\left( n^{\log _ba} \right) , d&<\log _ba\\ \end{aligned} \right.

2.3 归并排序​

归并排序的时间复杂度为 O(nlog⁡n)O(n\log n)。 伪代码如下：

function mergesort(a[1...n])
Input: an array a[1...n] of n numbers
Output: a[1...n] sorted in nondecreasing order
if n > 1:
    return merge(mergesort(a[1...⌊n/2⌋]), mergesort(a[⌊n/2⌋+1...n]))))
else:
    return a
    
function merge(x[1...p], y[1...q])
if p = 0: return y[1...q]
if q = 0: return x[1...p]
if x[1] ≤ y[1]:
    return [x[1]] + merge(x[2...p], y[1...q])
else:
    return [y[1]] + merge(x[1...p], y[2...q])

2.4 寻找中项​

寻找中项的时间复杂度为 O(n)O(n)。

伪代码如下：

function median(a[1...n])
Input: an array a[1...n] of n numbers
Output: the median of a[1...n]
if n = 1: return a[1]
choose a pivot p from a[1...n]
let L = {x ∈ a[1...n] | x < p}
let E = {x ∈ a[1...n] | x = p}
let G = {x ∈ a[1...n] | x > p}
if |L| ≥ ⌈n/2⌉: return median(L)
else if |L| + |E| ≥ ⌈n/2⌉: return p
else: return median(G)

2.5 矩阵乘法​

矩阵乘法的时间复杂度为 O(nlog⁡27)≈O(n2.81)O(n^{\log_2 7}) \approx O(n^{2.81})。

首先将 矩阵 AA 和 BB 分成四个子矩阵：

A=[A11A12A21A22],B=[B11B12B21B22]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}

然后计算以下七个矩阵：

M1=(A11+A22)(B11+B22)M2=(A21+A22)B11M3=A11(B12−B22)M4=A22(B21−B11)M5=(A11+A12)B22M6=(A21−A11)(B11+B12)M7=(A12−A22)(B21+B22)\begin{aligned} M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \\ M_2 &= (A_{21} + A_{22})B_{11} \\ M_3 &= A_{11}(B_{12} - B_{22}) \\ M_4 &= A_{22}(B_{21} - B_{11}) \\ M_5 &= (A_{11} + A_{12})B_{22} \\ M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \\ M_7 &= (A_{12} - A_{22})(B_{21} + B_{22}) \end{aligned}

最后将结果组合成矩阵 CC ：

C=[C11C12C21C22]C=\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix}

其中：

C11=M1+M4−M5+M7C12=M3+M5C21=M2+M4C22=M1−M2+M3+M6\begin{aligned} C_{11} &= M_1 + M_4 - M_5 + M_7 \\ C_{12} &= M_3 + M_5 \\ C_{21} &= M_2 + M_4 \\ C_{22} &= M_1 - M_2 + M_3 + M_6 \end{aligned}

2.6 FFT​

快速傅里叶变换（FFT）的时间复杂度为 O(nlog⁡n)O(n\log n)。

离散傅里叶变换

[X0X1X2⋮XN−1]=[111...11ωω2...ωN−11ω2ω4...ω2(N−1)⋮⋮⋮⋱⋮1ωN−1ω2(N−1)...ω(N−1)(N−1)][x0x1x2⋮xN−1]\left[ \begin{array}{c} X_0\\ X_1\\ X_2\\ \vdots\\ X_{N-1}\\ \end{array} \right] =\left[ \begin{matrix} 1& 1& 1& ...& 1\\ 1& \omega& \omega ^2& ...& \omega ^{N-1}\\ 1& \omega ^2& \omega ^4& ...& \omega ^{2(N-1)}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\ 1& \omega ^{N-1}& \omega ^{2(N-1)}& ...& \omega ^{(N-1)(N-1)}\\ \end{matrix} \right] \left[ \begin{array}{c} x_0\\ x_1\\ x_2\\ \vdots\\ x_{N-1}\\ \end{array} \right]

其中 ω\omega 为 nn 次单位根，ω=e−2πiN\omega =e^{-\frac{2\pi i}{N}}。

2.6.1 从系数表示法到点表示法(DFT)​

DFT，对于 nn 次多项式 f(x)=∑aixif(x) = \sum a_ix^i，总可以根据 ii 来进行划分：

f(x)=x2(∑a2ixi)+∑a2i+1xi=feven(x2)+xfodd(x2)f(x) = x^2\left( \sum a_{2i}x^i \right) + \sum a_{2i+1}x^i = f_{even}(x^2) + xf_{odd}(x^2)

由单位根的性质，ωn2=ωn/2\omega_n^{2} = \omega_{n/2}，所以

f(ωnk)=feven(ωn2k)+ωnkfodd(ωn2k)=feven(ωn/2k)+ωnkfodd(ωn/2k)\begin{aligned} f(\omega_n^k) &= f_{even}(\omega_n^{2k}) + \omega_n^kf_{odd}(\omega_n^{2k}) \\ &= f_{even}(\omega_{n/2}^k) + \omega_n^kf_{odd}(\omega_{n/2}^k) \end{aligned}

这就将规模减半了。

2.6.2 快速傅里叶变换​

两个多项式 A(x)A(x) 和 B(x)B(x) 的乘积 C(x)C(x) 可以通过以下步骤计算：