主定理

定理

假设我们有递推关系式(egin{aligned}T(n)=aTleft(frac n b ight)+f(n)end{aligned})其中(n)为问题规模，(a)为递推的子问题数量，(frac n b)为每个子问题的规模（假设每个子问题的规模基本一样），(f(n))为递推以外进行的计算工作。

关于符号问题

时间复杂度常见的符号就三个
(Theta)读作(theta)，音标为/'θi:tə/，表示紧贴，贴合等于的意思
(O)英语读音貌似是(omicron)，音标为/oumaik'rən/，表示的是最坏的时间复杂度，上界线，小于等于
(Omega)读作(omega)，音标为/'oumigə/，表示最低时间复杂度，下界线
其实也不进行很明显的区分，毕竟分析的时候都是考虑的最坏情况

Type 1

若存在常数(epsilon>0)使得(egin{aligned}f(n)=O(n^{log_b(a)-epsilon})end{aligned})，则(T(n)=Theta(n^{log_ba}))
举个栗子(T(n)=2T(frac n 2)+O(1)，则T(n)=O(n))
具体模型：二叉树遍历，其中(a=2,b=2,epsilon=1,f(n)=1,T(n)=O(n))
(T(n)=4T(frac n 2)+O(n)，则T(n)=O(n^2))

Type 2

若存在常数(kge0)(，使得)(f(n)=Theta (n^{log _{b}a}log ^{k}n))，则有(T(n)=Theta(n^{log_ba}log^{k+1}n))
举个栗子(T(n)=T(frac n 2)+O(1)，则T(n)=O(logn))
具体模型：二分，折半，其中(a=1,b=2,f(n)=1,k=0,T(n)=O(logn))
(T(n)=T(frac n 2)+O(logn)，则T(n)=O(log2n))
(T(n)=2T(frac n 2)+O(n)，则T(n)=O(nlogn))
具体模型：归并排序，考虑的是将序列分成两半进行处理，然后(O(n))进行合并，其中(a=2,b=2,f(n)=n,k=0,T(n)=O(nlogn))
(T(n)=2T(frac n 2)+O(nlogn)，则T(n)=O(nlog2n))

Type 3

若存在常数(epsilon>0)，使得(f(n)=Omega (n^{log _{b}(a)+epsilon }))同时存在常数(c<1)以及充分大的(n)满足(afleft({frac {n}{b}} ight)leq cf(n))，那么((Tleft(n ight)=Theta left(fleft(n ight) ight))
举个栗子(T(n)=T(frac n 2)+O(n)，则T(n)=O(n))
(T(n)=2T(frac n 2)+O(n^2)，则T(n)=O(n^2))

主定理无法处理的

举个栗子
(T(n)=2T(frac n 2)+O(logn)，则T(n)=O(n))
(T(n)=T(k)+T(n-k)+O(min(k,n-k))，则T(n)=O(nlogn))
具体模型：快排

例题

(Non-boring sequences)
一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
考虑一段区间：
如果这个区间中存在某个数，使得它在整段区间中出现次数为1，那么对于所有包含该数的子区间，该数都出现且仅出现1次。所以只需要分治处理这个数左右两端的子区间即可；
如果这个区间中不存在这样的数，那么它就是不合法的。
于是只需要想办法求出区间中只出现过一次的数即可。一个数在区间中只出现过1次，当且仅当它上一次出现的位置在区间左端，下一次出现的位置在区间右端。所以预处理左右出现的位置即可判断。
由于这个数不是恰好出现在区间中间的，所以找一次的时间复杂度应该设计为(O(较小的一段子区间的长度))。
具体方法：从左右两端向中间扫，扫到了就停止。这样找一次的复杂度一定是2倍较短区间长度。时间复杂度(O(nlogn))
也就是(T(n)=T(k)+T(n-k)+O(min(k,n-k))，则T(n)=O(nlogn))
【NOIP初赛2017】若某算法的计算时间表示为递推关系式：(egin{aligned}T(N)=2Tleft(frac N 2 ight)+Nlog Nend{aligned})，(T(1)=1)，则复杂度为
( m A .O(N) B .O(Nlog_2N) C.O(Nlog_2^2N) D.O(N^2))
就是(Type2)中(k=1)即可