graph LR
A[分治策略] --> B[基本框架]
A --> C[时间复杂度分析]
A --> D[经典案例]
B --> B1["分解:将问题划分为k个子问题"]
B --> B2["解决:递归解决子问题"]
B --> B3["合并:合并子问题解"]
C --> C1["通用递归式:<br>T(n) = aT(n/b) + D(n) + C(n)"]
C1 --> C11["a: 子问题数量"]
C1 --> C12["b: 规模缩小因子"]
C1 --> C13["D(n): 分解时间"]
C1 --> C14["C(n): 合并时间"]
C --> C2["分析方法"] --> C21["递归树法"] --> C211["每层代价累加"]
C2 --> C22["主定理"] --> C221["Case1/2/3判定"]
C2 --> C23["代入法"] --> C231["数学归纳证明"]
D --> D1["归并排序"] --> D11["T(n)=2T(n/2)+O(n) → O(n logn)"]
D --> D2["快速排序"] --> D21["最佳T(n)=O(n logn)<br>最差T(n)=O(n²)"]
D --> D3["二分查找"] --> D31["T(n)=T(n/2)+O(1) → O(logn)"]
D --> D4["Strassen矩阵乘法"] --> D41["T(n)=7T(n/2)+O(n²) → O(n^log₂7)"]
D --> D5["最近点对问题"] --> D51["T(n)=2T(n/2)+O(n) → O(n logn)"]
mermaid
算法引入#
在解决较困难问题时我们可以将问题拆解,直到拆解为规模足够小的问题,我们称之为基本情况。同时需要注意:子问题的规模不必是原问题规模的一个固定比例。例如:分治排序若每次将数组分为长度为n-1和1的两组,其递归时间复杂度为 T(n)=T(n−1)+O(1)
{{< notice info >}}
在设计分治算法时要特别注意边界条件的设置
{{< /notice >}}
对于几个常见例子:最大化连续区间和、传统矩阵分治乘法(相比BF无优化)、矩阵乘法Strassen算法等,本笔记只着重于Strassen算法的内容整理。
Strassen算法#
传统矩阵算法步骤如下:
Ci,j=k=1∑nAi,kBk,j⇒O(n3)
基本步骤如下:
- 将将n×n矩阵分割为4个(n/2)×(n/2)子矩阵
- 递归计算7个矩阵乘积
- 通过加减组合得到结果矩阵
接下来以2x2矩阵举例,其算法关键在于其计算的7个矩阵乘积
A=[A11 A21A12A22],B=[B11 B21B12B22]
M1 M2 M3 M4 M5 M6 M7=(A11+A22)(B11+B22)=(A21+A22)B11=A11(B12−B22)=A22(B21−B11)=(A11+A12)B22=(A21−A11)(B11+B12)=(A12−A22)(B21+B22)
C=[M1+M4−M5+M7 M2+M4M3+M5M1−M2+M3+M6]
其复杂度分析:
T(n)={O(1) 7T(n/2)+18(n/2)2当 n=1当 n>1
关键在于 T(n/2) 前的系数由传统方法的8降为了7,在大矩阵乘法计算时优势极为明显。接下来学习如何化简递推式。
分治算法时间复杂度的分析#
代入法#
- 猜测解的形式
- 使用数学归纳法证明
关键在于如何“猜”:Attention is all your need。但是存在一些启发式的方法帮助猜测;或者是先证明递归式较松的上界和下界,运用类似夹逼的思想逼近紧确界
递归树方法#
注意到,不是每个人都有很强的注意力,所以我们可以使用递归树方法计算。下面说明递归树计算方法:
首先构造 T(n)=aT(n/b)+f(n) 的递归树:
- 根节点:f(n) (当前层代价)
- 子节点:共 a 个分支,每个分支对应 T(n/b)
- 递归构造直到叶子结点 T(1)
第i层特征:
⎩⎨⎧递归深度:i 问题规模:n/bi 节点数:ai 每层总代价:ai⋅f(n/bi)
通过树的知识,我们容易确定树高: logbn
最后通过求和计算整棵树的代价:
T(n)=i=0∑logbn(ai⋅f(n/bi))
接下来举几个案例来更具体地说明:
归并排序#
T(n)=2T(n/2)+O(n)
T(n) =i=0∑log2ncn=cn×(log2n+1)=cnlog2n+cn=Θ(nlogn)
二分查找#
T(n)=T(2n)+c(c>0)
T(n) =i=0∑log2nc=c×(log2n+1)=clog2n+c=Θ(logn)
斐波那契数列#
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)
通过特征方程法求解齐次递推关系:
r2=r+1⇒r=21±5
得:
T(n)=A(21+5)n+B(21−5)n
由于
21+5≈1.618,21−5≈−0.618
当 n→∞ 负项可被忽略
T(n)≈A(1.618)n=O((21+5)n)⊂O(2n)
显然,这是一个效率极低的方法,记忆化递归的方法可以使用哈希表存储已计算结果,减少重复计算
更复杂的递推式#
接下来用一个较为复杂的递推式来说明:
T(n)=3T(4n)+n2=i=0∑log4n(163)in2
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=1316[1−(163)log4n+1]
(163)log4n=eln(3/16)⋅log4n=nlog4(3/16)
S=1316[1−163⋅n−2+log43]
S=1316−133⋅n−2+log43
观察指数项:
−2+log43≈−1.2075<0
所以 n→∞ 时有
T(n)=n2⋅S=n2(1316−o(1))=Θ(n2)
主定理#
先给出主定理:
对于形如 T(n)=aT(n/b)+f(n) 形式的递推式,其中 f(n)=Θ(nklogpn),a≥1,b>1,k≥0
T(n)=⎩⎨⎧Θ(nlogba) Θnlogba⋅⎩⎨⎧logp+1n loglogn 1p>−1p=−1p<−1 Θ(nk⋅{logpn 1p≥0p<0)若 a>bk若 a=bk若 a<bk
计算时直接代入即可
对于这几种情况的直观解释如下:
- 叶子主导型:这种情况中每个节点的子节点极多,子节点的个数对复杂度影响大
- 均衡型:这种情况二者对时间复杂度的影响程度相近
- 根主导型:合并操作的时间复杂度较大,对最终复杂度影响大