ghj1222
先介绍几个符号的含义。
符号Theta)，读音西塔，既是上界也是下界，等于，严格贴紧。
符号O)，读音殴，表示上界，小于等于，贴紧未知。
符号o)，读音也是殴，小于，不贴紧。
符号Omega)，读音偶眯嘎，表示下界，大于等于，贴紧未知。
符号omega)，读音也是偶眯嘎，表示下界，大于，不贴紧。
上面的“贴紧”是我根据tight翻译过来的不是很准确啊)，大概就是是否严格等于的意思吧。
意思就是Theta)是平均时间复杂度，O)是最坏情况下的复杂度，Omega)是最好情况下的复杂度。
假设我们有递推关系式：
egin{aligned}Tn)=aTleftfrac n bight)+fn)end{aligned})
其中，n)为问题的规模、a)为递推下子问题的数量，egin{aligned}frac n bend{aligned})为每个子问题的规模，fn))为递推后做的额外的计算工作。
1.假设存在常数epsilon>0)，使得fn)=On^{log_ba)-epsilon}))，则Tn)=Thetan^{log_ba}))。
具体意思是fn)的上界是n的幂次，且log_ba))比这个幂次要大，则时间复杂度为这个n的log_ba))次。
例子：二叉树的遍历。egin{aligned}Tn)=2Tleftfrac n 2ight)+Theta1)end{aligned})。其中a=2)，b=2)，fn)=1)，此时epsilon=1)。Tn)=Thetan))。
2.假设存在常数kge0)，使得fn)=Theta n^{log _{b}a}log ^{k}n))，则Tn)=Thetan^{log_ba}log^{k+1}n))。
具体意思是fn)是n的log_ba))次，再乘以一个log，则复杂度是fn)的复杂度再乘以一个log。
例子：归并排序。egin{aligned}Tn)=2Tleftfrac n 2ight)+Thetan)end{aligned})。其中a=2)，b=2)，fn)=n)，此时k=0)。Tn)=Thetanlog_2n))。
例子：二分搜索（折半搜索）。egin{aligned}Tn)=Tleft{frac {n}{2}}ight)+Theta 1)end{aligned})，其中a=1)，b=2)，fn)=1)，此时k=0)，则Tn)=Thetalog_2n))。
3.假设存在常数epsilon >0) ，有fn)=Omega n^{log _{b}a)+epsilon }))，同时存在常数c<1)以及充分大的n)满足 afleft{frac {n}{b}}ight)leq cfn))那么 Tleftnight)=Theta leftfleftnight)ight))。
这个感觉没啥用啊。。。
【例题】
【NOIP2017初赛】若某算法的计算时间表示为递推关系式：
egin{aligned}TN)=2Tleftfrac N 2ight)+Nlog Nend{aligned})，T1)=1)，则该算法的时间复杂度为______________________________________________________。
m A .ON) B .ONlog_2N) C.ONlog_2^2N) D.ON^2))
【解析】套用情况2中的k=1的情况，则Tn)=ThetaNlog_2^2N))，选C
【NOIP2016初赛】若某算法的计算时间表示为递推关系式：
egin{aligned}TN)=2Tleftfrac N 4ight)+sqrt Nend{aligned})，T1)=1)，则该算法的时间复杂度为______________________________________________________。
m A .ON) B .Osqrt N) C.Osqrt Nlog_2N) D.ON^2))
【解析】套用情况2中的k=0的情况，则Tn)=ThetasqrtN)log_2N))，选C
【NOIP2015初赛】某算法的计算时间表示为递推关系式：
TN)=TN-1)+N)，T0)=1)。则该算法的时间复杂度为______________________________________________________。
m A .Olog_2^2N) B .ONlog_2 N) C.ON) D.ON^2))
【解析】难道这个就要用主定理了？容易推导出egin{aligned}TN)=T0)+1+…+n=1+frac{N*N+1)}{2}end{aligned})，则时间复杂度为ON^2))，选D
【总结】
NOIP初赛考察了3年的时间复杂度分析，其中两年用到了主定理。其实你不会主定理也没事儿，只要能找几个特殊值带入，并根据符号O)的意义排除选项即可。