算法设计与分析.05.分治算法 (2)
分治 (2)
- divide and conquer
master theorem
- 主定理
形式
\[ T(n)=aT(\dfrac{n}{b})+f(n) \]
\[ T(0)=0,T(1)=\Theta(1) \]
- 参数
- \(a\ge1\):子问题个数
- \(b\ge2\):子问题规模变小
- \(f(n)\ge0\):divide and merge
递归树
- \(a\) = branching factor.
- \(a^i\) = number of subproblems at level \(i\)
- \(1 + \log_b n\) levels
- \(n / b^i\) = size of subproblem at level \(i\)
特例
\[ T(n)=aT(\dfrac{n}{b})+n^c,n=b^k,k\in\mathrm{N} \]
- 根据递归树
\[ \begin{aligned} T(n) &=a^{\log_b{n}}+\sum_{i=0}^{\log_b{n}-1}a^i(\dfrac{n}{b^i})^c\\ &=n^{\log_b{a}}+n^c\sum_{i=0}^{\log_b{n}-1}r^i\\ &=n^c\sum_{i=0}^{\log_b{n}}r^i\\ \end{aligned} \]
- \(r=\dfrac{a}{b^c}\) 是一个关键变量
主定理
- 证明思路
- 先证明 n 是 b 的整数次幂的情况(上面的特例)
- 扩展到实数域上
- 处理取整 \(\lceil\rceil,\lfloor\rfloor\)
- 最多多出来两层
\[ \lceil{n/b}\rceil<{n/b}+1 \]
\[ \begin{aligned} \lceil{\lceil{\lceil{n/b}\rceil/b}\rceil/b}\rceil &<{n/b^2}+(1+1/b+1/b^2)\\ &\le{n/b^2}+2 \end{aligned} \]
- 扩展
- \(O\) 取代 \(\Theta\)
- \(\Omega\) 取代 \(\Theta\)
- 扩展初始区域:\(T(n)=\Theta(1),n\le n_0\)
局限
- \(a\) 是 \(n\) 的函数
- \(a<1\)
- \(f(n)\) 不满足 \(\Theta(n^c)\) 的形式
- \(f(n)=n\log n\)
通用定理
integer multiplication
- 大整数乘法
大整数加法
- Addition
- Given two n-bit integers a and b, compute a + b
- Subtraction
- Given two n-bit integers a and b, compute a – b.
- Grade-school algorithm
- \(\Theta(n)\) 个操作
- optimal
Grade-school 算法
- Grade-school algorithm (long multiplication)
- \(O(n^2)\)
- optimal?\({\color{red}\mathrm{X}}\)
- Conjecture(猜想)
- [Kolmogorov 1956] Grade-school algorithm is optimal
- Theorem.
- [Karatsuba 1960] Conjecture is false
- Conjecture(猜想)
分治算法
- x,y 分别划分为高 n/2 位和低 n/2 位,计算 4 个乘法,然后做加法
\[
T(n)=4T(\lceil\dfrac{n}{2}\rceil)+\Theta(n)\Rightarrow T(n)=\Theta(n^2)
\]
Karatsuba multiplication
- 分治算法的优化
\[ (bc+ad)=ac+bd-(a-b)(c-d) \]
- 此时乘法计算次数为 3
\[ T(n)=3T(\lceil\dfrac{n}{2}\rceil)+\Theta(n)\Rightarrow T(n)=\Theta(n^{\log_{2}{3}}) \]
整数计算
- \(M(n)\) 表示整数乘法复杂度
- 发展历程
matrix multiplication
- 矩阵乘法
向量乘法
- \(a,b\in\mathrm{R}^n\)
- Grade-school:\(O(n)\)
- asymptotically optimal
矩阵乘法
- \(A,B\in\mathrm{R}^{n\times n}\)
- Grade-school:\(O(n^3)\)
- optimal?\({\color{red}\mathrm{X}}\)
分块矩阵乘法
\[
T(n)=8T(\dfrac{n}{2})+\Theta(n^2)\Rightarrow T(n)=\Theta(n^3)
\]
- 并没有改进
Strassen’s trick
- 神奇!
\[ T(n)=7T(\dfrac{n}{2})+\Theta(n^2)\Rightarrow T(n)=\Theta(n^{\log_{2}{7}}) \]
- 实际操作:当矩阵大小不是 2 的幂次的时候,补 0
- 问题
- Sparsity
- Caching
- n not a power of 2
- Numerical stability(浮点数计算)
- Non-square matrices
- Storage for intermediate submatrices
- Crossover to classical algorithm when n is “small”
- Parallelism for multi-core and many-core architectures
- 规模足够大的时候,算法优势体现出来
理论
- Multiply two 2-by-2 matrices with 7 scalar multiplications?
- Yes! [Strassen 1969]
- 子矩阵乘法次数为 7
- Multiply two 2-by-2 matrices with 6 scalar multiplications?
- Impossible. [Hopcroft–Kerr, Winograd 1971]