利用主定理来计算程序的时间复杂度

第二版前言

这篇文章在 $2022/10/7$ 重新进行了一些排版上的调整，最开始的原因是笔者认为这篇文章写的还算不错，而且里面涉及的知识以后可能还会用上，所以又传了一遍。

前言

$\text{Master}$ 定理，又称主定理，用于程序的时间复杂度计算，核心思想是分治，近几年 $\text{Noip}$ 常考时间复杂度的题目，都需要主定理进行运算。

前置

我们常见的程序时间复杂度有：

$O(n)/O(n^2)/O(nlog_2n)/O(2^n)$ 等等...

我们叫它程序的渐进时间复杂度，例如一段程序执行这样的循环：

for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        sum+=a[i][j];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        pai*=a[i][j];

显然，这段代码一共运行了 $n^3+2n^2$ 次，我们将它的渐进时间复杂度写作 $O(n^3)$，即保留最高项但忽略其系数。

约定：一般我们将 $log_2n$ 写作 $logn$ ，将 $logn\cdot logn$ 写作$log^2n$

算时间复杂度有什么用呢？一般来说，在比赛时我们将知道程序的时间限制，一般为 $1s$ ，我们可以通过粗略计算程序时间复杂度来判断程序是否能在 $1s$ 通过，否则会 $\text{TLE}$（$\text{Time Limit Exceeded}$）。

时间复杂度	$1s$内稳过的范围	极限范围（危险）
$O(1)$	$\infty$	$\infty$
$O(wys)$	$\infty$	$\infty$
$O(logn)$	$\infty$	$\infty$
$O(n)$	$5\times10^7$	$10^8$
$O(nlogn)$	$5\times 10^5$	$10^6$
$O(n^2)$	$5000$	$10000$
$O(n^3)$	300	500
$O(2^n)$	25	27
$O(n!)$	11	11（稳过）
$O(n^n)$	8	8（稳过）

PS：由于程序存在常数因子，极限范围不一定能过，除非你是欧洲人。

大概来说，如果你算出的渐进时间复杂度量化后在千万级别[ $n\times10^7$ ]，基本上是很稳的

对于非递归程序时间复杂度的运算方法，比较简单粗暴的方法是数循环。但这种方法并不一定始终正确，如 $\text{NOIP2017PJT4}$ 的二分答案是 $O(logn)$ 复杂度的，$\text{dp}$ 的转移是执行 $n$ 次的，而对于单调队列，每个元素至多进队一次，出队一次，最多有 $2n$ 次操作，$\text{dp}$ 的总操作次数应该是将它们加在一起，共 $3n$ 次操作，时间复杂度为 $O(n)$，而不是 $O(n^2)$，总复杂度为 $O(nlogn)$ ，与之类似的还有 $kmp$ 算法的时间复杂度。（PS: $\text{kmp}$ 算法的时间复杂度至今仍存在争议，我们一般将其视作 $O(n)$ 的）

正文

介绍 $\text{master}$ 定理前，首先要知道几个符号

1. $T(n)$ 表示时间复杂度，可以这样表示：$T(n)=$一个单项式，例如：

$T(n)=2T(n/2)+f(n)$

2. $\Theta$ 读音：$theta$，表示等于
3. $O$ 读音：$big\ oh$，表示小于等于
4. $o$ 读音：$small\ oh$，表示小于
5. $\Omega$ 读音：$big\ omega$，表示大于等于
6. $\omega$ 读音：$small\ omega$，表示大于

主定理是怎么表示的呢？

• 我们目前有一个规模为$n$的问题
• 通过分治，我们将问题分成 $a$ 个规模为 $\frac{n}{b}$，每次递归将带来 $f(n)$ 的额外计算
• 于是得到关系式：

$T(n)=aT(\frac{n}{b})+f(n)$

此外，我们还要定义一个 $C_{crit}$，它是这样计算的：

$C_{crit}=log_ba$

那么有：

$1$.

• 当 $f(n)=O(n^c)$，且 $c<c_{crit}$ 时有：$T(n)=\Theta(n^{c_{crit}})$
• 例子：
• $T(n)=8T(\frac{n}{2})+1000n^2$
• 此时 $a=8,b=2,f(n)=1000n^2$
• 当 $c=2$ 时，$f(n)=O(n^2)$
• 又因为 $C_{crit}=log_ba=3>c$
• 所以 $T(n)=\Theta(n^{log_ba})=\Theta(n^3)$

$2$.

• 当 $f(n)=O(n^c)$，且 $c>c_{crit}$ 时有：$T(n)=\Theta(f(n))$
• 例子：
• $T(n)=2T(\frac{n}{2})+n^2$
• 此时 $a=2,b=2,f(n)=n^2$
• 当 $c=2$ 时，$f(n)=O(n^2)$
• 又因为 $c_{crit}=log_ba=1<c$
• 所以 $T(n)=\Theta(f(n))=\Theta(n^2)$

$3$.

• 若存在一个非负整数 $k$，使得 $f(n)=\Theta(n^{c_{crit}}log^kn)$
• 那么 $T(n)=\Theta(n^{c_{crit}}log^{k+1}n)$
• 例子：
• $T(n)=2T(\frac{n}{2})+10n$
• 此时 $a=2,b=2,f(n)=10n$；$c_{crit}=log_ba=1$
• 当 $k=0$ 时 $f(n)=\Theta(n^1log^0n)=\Theta(n)$
• 所以 $T(n)=\Theta(n^1log^1n)=\Theta(nlogn)$

练手题

• 首先，我们知道 $a=2,b=4,f(n)=\sqrt{n}=n^{\frac{1}{2}}$；$c=\frac{1}{2},c_{crit}=log_42=\frac{1}{2}$
• 当 $k=0$ 时，满足条件3，所以，$T(n)=O(\sqrt nlogn)$，选 $C$

---

$T(n)$
$=T(n-1)+n-1+n$
$=T(n-2)+n-2+n-1+n$
$=...$
$=T(0)+0+1+2+...+n-2+n-1+n$
$=1+\frac{n\times (n+1)}{2}$
$=O(n^2)$

选择 $D$

---

• 假设 $g(i)$，为计算 $F(i)$ 的次数，因为 $F(i)=F(i-1)+F(i-2)$ 所以 $g(i)=g(i-1)+g(i-2)$
• 因为 $F(1)=g(1)=1,F(2)=g(2)=1$，所以 $g(n)=F(n)$
• 则:

$T(n)=g(n)=F(n)=O(F(n))$

选择 $D$

完结

这和大家能够平安过初赛！