分治法学习笔记

Posted on

MIT《算法导论》课程第3课《分治法》学习笔记.

分治法

  1. Divide 分：将问题分为更小的子问题
  2. Conquer 治：递归地解决每一个子问题
  3. Combine

归并排序

  1. 分：将序列分为左边$[1, \frac{n}{2}]$和右边$[\frac{n+1}{2}, n]$两个区间
  2. 治：递归地对两个区间分别排序
  3. 合

运行时间：


$$
T(n)=2T(\frac{n}{2})+\Theta(n)$，由 Master Method 中的 Case 2 得知$T(n)=\Theta(n\log n)
$$

二分查找

  1. 将序列分为两部分
  2. 递归地查找
  3. 合

运行时间：


$$
T(n)=T(\frac{n}{2})+\Theta(1)
=O(\log n)
$$

Powering a number 乘方问题

给出一个数$x$，给出整数$n \ge 0$，计算$x^n$。

朴素算法


$$
x^n = x \times x \times x \times \dots \times x （共有n个x）
$$

运行时间复杂度$\Theta(n)$

分治方法


$$
x^n=x^{n/2} \times x^{n/2}，如果n为偶数
$$

$$
x^n=x^{(n-1)/2} \times x^{(n-1)/2} \times x，如果n为奇数
$$

$$
\begin{align}
T(n)&=T(\frac{n}{2})+\Theta(1)\
&=\Theta(\log n)
\end{align}
$$

Fibonacci数列

递归方法

递归地计算求解，时间复杂度$\Omega(\phi^n)$，其中$\phi=\frac{1 + \sqrt 5}{2}$。

自下而上的解决方法

依次计算$F_0, F_1, F_2, \dots， F_n$（动态规划的思想）

时间复杂度$\Theta(n)$。

朴素递归分治


$$
F_n = \frac{\phi^n}{\sqrt 5}四舍五入取整
$$

实际难以计算。

平方递归方法


$$
\begin{bmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}
^n
$$

证明


  1. $$
    \begin{bmatrix}
    1 & 1 \
    1 & 0
    \end{bmatrix}
    =
    \begin{bmatrix}
    F_{2} & F_1 \
    F_1 & F_{0}
    \end{bmatrix}
    $$

$$
\begin{bmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
F_{n} & F_{n-1} \
F_{n-1} & F_{n-2}
\end{bmatrix}
\times
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}
$$

由1和2，有


$$
\begin{bmatrix}
F_{n+1} & F_n \
F_n & F_{n-1}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}
^n
$$

矩阵乘法

输入：$A={a_{ij}},B={b_{ij}},i,j=1,2,\dots,n$

输出：$C={c_{ij}}=A \cdot B$，
$
c_{ij}=\sum\limits_{k=1}\limits^{n} a_{ik}b_{kj}
$

标准方法：直接计算

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

1
2
3
4
5
for i = 1 : n
  for j = 1 : n
    c_ij=0;
    for k = 1 : n
      c_ij += a_ik * b_kj

矩阵分块

$n \times n$阵划分为$2 \times 2$阵，其中每个元素都是$\frac{n}{2} \times \frac{n}{2}$阵。

于是


$$
C =
\begin{bmatrix}
r & s \
t & u
\end{bmatrix}
=
{
\begin{bmatrix}
a & b \
c & d
\end{bmatrix}
}
\cdot
{
\begin{bmatrix}
e & f \
g & h
\end{bmatrix}
}
$$

$$
r = ae + bg
$$

$$
s = af + bh
$$

$$
t = ce + dg
$$

$$
u = cf + dh
$$

需要8次递归相乘，4次递归相加。

于是


$$
\begin{align}
T(n) & = 8 \cdot T(\frac{n}{2}) + \Theta(n^2) \
& = Theta(n^3)
\end{align}
$$

Strassen’s Algorithm

与矩阵分块相比，减少递归乘法的次数。

时间复杂度为


$$
\begin{align}
T(n) &= 7 \cdot T(\frac{n}{2}) + \Theta(n^2) \
&= \Theta(n^{\lg 7}) \
&= O(n^{2.81})
\end{align}
$$