Master Theorem

证明定理2, 3

定理2

\[\displaystyle \sum_{j=0}^{\log_b N-1}a^j(\frac{N}{b^j})^{\log_b a}=\sum_{j=0}^{\log_b N-1}a^j(\frac{N^{\log_b a}}{a^j})=\log_b N\times N^{\log_b a}\]

\[\therefore T(N) = O(\log_b N\times N^{\log_b a}) = O(N^{\log_b a}\lg N)\]

例

\(T(n)=T(\alpha n) + T((1-\alpha)n)+\Theta(n^2)\), 其中 \(0<\alpha<1\), 则复杂度是多少

不妨设 \(\alpha>\frac12\)

假设最大层数是 \(k\), 那么 \(\alpha^kn=1\), \(k=\log_{\frac1\alpha}n\)

则按照满二叉树处理，叶子的贡献为 \(2^k=2^{\log_{\frac1\alpha}n}=n^{\log_{\frac1\alpha}2}\)

同时每层的根贡献为 \([\alpha^2 + (1-\alpha)^2]^in^2\), 所以根的贡献为 \(\sum_{i=0}^k [\alpha^2 + (1-\alpha)^2]^in^2=\frac{1-[\alpha^2 + (1-\alpha)^2]^k}{1-[\alpha^2 + (1-\alpha)^2]}n^2\)

当 \(k\) 较大时可以看成 \(\lim_{k\to\infty}\frac{1-[\alpha^2 + (1-\alpha)^2]^k}{1-[\alpha^2 + (1-\alpha)^2]}n^2=\frac{1}{2\alpha(1-\alpha)}n^2\)

所以最后复杂度为 \(O(\max(n^{\log_{\frac1\alpha}2}, \frac{1}{2\alpha(1-\alpha)}n^2))\)

这里 \(n^{\log_{\frac1\alpha}2}\) 是一个不紧的上界，这是由于 \(k=\log_{\frac1\alpha}n\) 取的是 \(\alpha > \frac12\) 时的值，而递归树的 \(1-\alpha < \frac12\) 的那一侧收敛更快，实际没有这么多层

如果按照这样分析，可以看出当 \(\alpha > \frac{1}{\sqrt2}\) 时， \(n^{\log_{\frac1\alpha}2}\) 就大于 \(n^2\) 了，用主定理也可以得到这样的结论

但是这是错的

仔细想想，可以想到 \(\alpha\) 越大， \(1-\alpha\) 的那一侧收敛越快，实际树会越来越不满

用这段代码观察实际表现:

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+10;
int n;
int a, b;
double alpha;
void T(int n){
    if(n <= 1){
        ++a;
        return;
    }
    b += n*n;
    T((int)(alpha*n));
    T((int)((1-alpha)*n));
}
void solve() {
    n = 1000000;
    alpha = 0.50;
    T(n);
    int c = ceil((1.0/2.0/alpha/(1.0-alpha)));
    printf("%lld\n%lld\n%lld\n", (n*n*c), a, b);
}
signed main() {
    solve();
    return 0;
}

结果：

\(\alpha\)	节点数\(n\)	叶实际贡献	根实际贡献	\(O(\frac{1}{2\alpha(1-\alpha)}n^2)\)估测值
0.50	1000000	524288	1999988054464	2000000000000
0.80	1000000	704696	3124937981706	4000000000000
0.98	1000000	825545	25507183430930	26000000000000
0.50	1024	1024	2095104	2097152

可以看到，叶实际贡献是 \(O(n)\) 的，所以复杂度应该为 \(O(\frac{1}{2\alpha(1-\alpha)}n^2)\)

至于叶实际贡献怎么推导，这里只是从实验角度给出他的实际表现，实际计算上界麻烦，就不算了

Strassen

简单分治

将一个大矩形分成 \(4\) 个小矩形计算，将 \(C=A\cdot B\) 分解为 \(C_{ij}=A_{i1}\cdot B_{1j} + A_{i2}\cdot B_{2j}\)

一共四个小 \(C_{ij}\), 总共 \(8\) 次乘法

那么有递归式 \(T(N) = 8T(N/2) + \Theta(N^2)\), 其中 \(\Theta(N^2)\) 是矩阵加法的时间

根据主定理得出 \(T(N)=\Theta(N^3)\), 相比普通矩阵乘法并没有实质提升，反而常数增大

玄学操作

我们同样对 \(A,B,C\) 分出 \(4\) 个子矩阵，然后创建 \(10\) 个新的小矩阵 \(S_1\cdots S_{10}\), 其中每个矩阵都是由 \(A,B\) 的子矩阵加/减得到

然后对 \(14\) 个矩阵两两相乘，得出 \(7\) 个小矩阵 \(P_1\cdots P_7\)

最后有 \(C_{11}=P_5+P_4-P_2+P_6\)

\(C_{12}=P_1+P_2\)

\(C_{21}=P_3+P_4\)

\(C_{22}=P_5+P_1-P_3-P_7\)

具体构造太复杂，参见算法导论

但是

这样的递归式会变成：

\(T(N) = 7T(N/2) + \Theta(N^2)\), 这里所有的加减法都是 \(\Theta(N^2)\) 的

根据主定理，我们有 \(T(N)=\Theta(N^{\log_2 7})=O(N^{2.81})\)