Master定理学习笔记

前言

$Master$定理，又称主定理，用于程序的时间复杂度计算，核心思想是分治，近几年$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³⁺²ⁿ2$次，我们将它的渐进时间复杂度写作$O(n^{3)$，即保留最高项但忽略其系数，约定：一般我们将$log_2n$写作$logn$，将$logn*logn$写作$log}2n$

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

时间复杂度	$1s$内稳过的范围	极限范围（危险）
$O(1)$	$infty$	$infty$
$O(wys)$	$infty$	$infty$
$O(logn)$	$infty$	$infty$
$O(n)$	$5 imes10^7$	$10^8$
$O(nlogn)$	$5 imes 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 imes10^7$]，基本上是很稳的

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

正文

介绍$master$定理前，首先要知道一个符号

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

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

$Theta$ 读音：$theta$，表示等于
$O$ 读音：$big oh$，表示小于等于
$o$ 读音：$small oh$，表示小于
$Omega$ 读音：$big omega$，表示大于等于
$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^1log0n)=Theta(n)$

所以$T(n)=Theta(n^1log1n)=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 imes (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$

完结

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