xy0v0's Blog

Back

算法引入#

在解决较困难问题时我们可以将问题拆解,直到拆解为规模足够小的问题,我们称之为基本情况。同时需要注意:子问题的规模不必是原问题规模的一个固定比例。例如:分治排序若每次将数组分为长度为n-1和1的两组,其递归时间复杂度为 T(n)=T(n−1)+O(1)T(n) = T(n-1) + O(1)

{{< notice info >}} 在设计分治算法时要特别注意边界条件的设置 {{< /notice >}}

对于几个常见例子:最大化连续区间和、传统矩阵分治乘法(相比BF无优化)、矩阵乘法Strassen算法等,本笔记只着重于Strassen算法的内容整理。

Strassen算法#

传统矩阵算法步骤如下:

Ci,j=∑k=1nAi,kBk,j⇒O(n3)C_{i,j} = \sum_{k=1}^{n} A_{i,k}B_{k,j} \quad \Rightarrow O(n^3)

基本步骤如下:

  1. 将将n×n矩阵分割为4个(n/2)×(n/2)子矩阵
  2. 递归计算7个矩阵乘积
  3. 通过加减组合得到结果矩阵

接下来以2x2矩阵举例,其算法关键在于其计算的7个矩阵乘积

A=[A11A12 A21A22],B=[B11B12 B21B22]A = \begin{bmatrix} A_{11} & A_{12} \\\ A_{21} & A_{22} \end{bmatrix}, \quad B = \begin{bmatrix} B_{11} & B_{12} \\\ B_{21} & B_{22} \end{bmatrix} M1=(A11+A22)(B11+B22) M2=(A21+A22)B11 M3=A11(B12−B22) M4=A22(B21−B11) M5=(A11+A12)B22 M6=(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} C=[M1+M4−M5+M7M3+M5 M2+M4M1−M2+M3+M6]C = \begin{bmatrix} M_1+M_4-M_5+M_7 & M_3+M_5 \\\ M_2+M_4 & M_1-M_2+M_3+M_6 \end{bmatrix}

其复杂度分析:

T(n)={O(1)当 n=1 7T(n/2)+18(n/2)2当 n>1T(n) = \begin{cases} O(1) & \text{当 } n=1 \\\ 7T(n/2) + 18(n/2)^2 & \text{当 } n>1 \end{cases}

关键在于 T(n/2)T(n/2) 前的系数由传统方法的8降为了7,在大矩阵乘法计算时优势极为明显。接下来学习如何化简递推式。

分治算法时间复杂度的分析#

代入法#

  1. 猜测解的形式
  2. 使用数学归纳法证明

关键在于如何“猜”:Attention is all your need。但是存在一些启发式的方法帮助猜测;或者是先证明递归式较松的上界和下界,运用类似夹逼的思想逼近紧确界

递归树方法#

注意到,不是每个人都有很强的注意力,所以我们可以使用递归树方法计算。下面说明递归树计算方法:

首先构造 T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) 的递归树:

  • 根节点:f(n)f(n) (当前层代价)
  • 子节点:共 aa 个分支,每个分支对应 T(n/b)T(n/b)
  • 递归构造直到叶子结点 T(1)T(1)

第i层特征:

{递归深度:i 问题规模:n/bi 节点数:ai 每层总代价:ai⋅f(n/bi)\begin{cases} 递归深度: i \\\ 问题规模: n/b^i \\\ 节点数: a^i \\\ 每层总代价: a^i \cdot f(n/b^i) \end{cases}

通过树的知识,我们容易确定树高: log⁡bn\log_b n

最后通过求和计算整棵树的代价:

T(n)=∑i=0log⁡bn(ai⋅f(n/bi))T(n) = \sum_{i=0}^{\log_b n} \left( a^i \cdot f(n/b^i) \right)

接下来举几个案例来更具体地说明:

归并排序#

T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n) T(n)=∑i=0log⁡2ncn =cn×(log⁡2n+1) =cnlog⁡2n+cn =Θ(nlog⁡n)\begin{align*} T(n) &= \sum_{i=0}^{\log_2 n} cn \\\ &= cn \times (\log_2 n + 1) \quad \\\ &= cn\log_2n + cn \\\ &= \Theta(n\log n) \end{align*}

二分查找#

T(n)=T(n2)+c(c>0)T(n) = T\left(\frac{n}{2}\right) + c \quad (c>0) T(n)=∑i=0log⁡2nc =c×(log⁡2n+1) =clog⁡2n+c =Θ(log⁡n)\begin{align*} T(n) &= \sum_{i=0}^{\log_2 n} c \\\ &= c \times (\log_2 n + 1) \\\ &= c\log_2n + c \\\ &= \Theta(\log n) \end{align*}

斐波那契数列#

graph TD
  L0["c (层0)"] --> L1["T(n-1)"]
  L0 --> L2["T(n-2)"]
  L1 --> L3["T(n-2)"]
  L1 --> L4["T(n-3)"]
  L2 --> L5["T(n-3)"]
  L2 --> L6["T(n-4)"]
mermaid
T(n)=T(n−1)+T(n−2)+c(c>0)T(n) = T(n-1) + T(n-2) + c \quad (c>0 )

通过特征方程法求解齐次递推关系:

r2=r+1⇒r=1±52r^2 = r + 1 \quad \Rightarrow \quad r = \frac{1 \pm \sqrt{5}}{2}

得:

T(n)=A(1+52)n+B(1−52)nT(n) = A\left(\frac{1+\sqrt{5}}{2}\right)^n + B\left(\frac{1-\sqrt{5}}{2}\right)^n

由于

1+52≈1.618,1−52≈−0.618\frac{1+\sqrt{5}}{2} \approx 1.618, \quad \frac{1-\sqrt{5}}{2} \approx -0.618

当 n→∞n \rightarrow \infty 负项可被忽略

T(n)≈A(1.618)n=O((1+52)n)⊂O(2n)T(n) \approx A(1.618)^n = O\left( \left(\frac{1+\sqrt{5}}{2}\right)^n \right) \subset O(2^n)

显然,这是一个效率极低的方法,记忆化递归的方法可以使用哈希表存储已计算结果,减少重复计算

更复杂的递推式#

接下来用一个较为复杂的递推式来说明:

T(n)=3T(n4)+n2=∑i=0log⁡4n(316)in2T(n) = 3T(\frac n4)+n^2 = \sum_{i=0}^{\log_4 n} \left( \frac{3}{16} \right)^i n^2
graph TD
  L0["n²(第0层)"] --> L1A["(n/4)²"]
  L0 --> L1B["(n/4)²"]
  L0 --> L1C["(n/4)²"]
  L1A --> L2A["(n/16)²"]
  L1A --> L2B["(n/16)²"]
  L1A --> L2C["(n/16)²"]
mermaid

首先展开有限级数,运用等比数列求和公式

S=1613[1−(316)log⁡4n+1]S = \frac{16}{13}\left[1 - \left(\frac{3}{16}\right)^{\log_4 n + 1}\right] (316)log⁡4n=eln⁡(3/16)⋅log⁡4n=nlog⁡4(3/16)\left(\frac{3}{16}\right)^{\log_4 n} = e^{\ln(3/16) \cdot \log_4 n} = n^{\log_4(3/16)} S=1613[1−316⋅n−2+log⁡43]S = \frac{16}{13}\left[1 - \frac{3}{16} \cdot n^{-2 + \log_4 3}\right] S=1613−313⋅n−2+log⁡43S = \frac{16}{13} - \frac{3}{13} \cdot n^{-2 + \log_4 3}

观察指数项:

−2+log⁡43≈−1.2075<0-2 + \log_4 3 \approx -1.2075 < 0

所以 n→∞n \rightarrow \infty 时有

T(n)=n2⋅S=n2(1613−o(1))=Θ(n2)T(n) = n^2 \cdot S = n^2 \left( \frac{16}{13} - o(1) \right) = \Theta(n^2)

主定理#

先给出主定理:

对于形如 T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) 形式的递推式,其中 f(n)=Θ(nklog⁡pn),a≥1,b>1,k≥0f(n)=\Theta(n^k \log^p n), a \ge 1, b > 1, k \ge 0

T(n)={Θ(nlog⁡ba)若 a>bk Θ(nlog⁡ba⋅{log⁡p+1np>−1 log⁡log⁡np=−1 1p<−1)若 a=bk Θ(nk⋅{log⁡pnp≥0 1p<0)若 a<bk\begin{equation*} T(n) = \begin{cases} \Theta\left(n^{\log_b a}\right) & \text{若 } a > b^k \\\ \Theta\left(n^{\log_b a} \cdot \begin{cases} \log^{p+1} n & p > -1 \\\ \log \log n & p = -1 \\\ 1 & p < -1 \end{cases}\right) & \text{若 } a = b^k \\\ \Theta\left(n^k \cdot \begin{cases} \log^p n & p \geq 0 \\\ 1 & p < 0 \end{cases}\right) & \text{若 } a < b^k \end{cases} \end{equation*}

计算时直接代入即可

对于这几种情况的直观解释如下:

  1. 叶子主导型:这种情况中每个节点的子节点极多,子节点的个数对复杂度影响大
  2. 均衡型:这种情况二者对时间复杂度的影响程度相近
  3. 根主导型:合并操作的时间复杂度较大,对最终复杂度影响大

分治策略与时间复杂度计算

https://www.xy0v0.top/blog/1739193994
Author xy0v0 Published at Copyright CC BY-NC-SA 4.0