主定理主定理是用来分析分治算法递归式的渐进时间复杂度在初赛中经常考到递归式形如T(n)aT(n/b)f(n)T(n)aT(n/b)f(n)T(n)aT(n/b)f(n)。有三种情形f(n)f(n)f(n)增速较慢若∃ϵ0\exist\epsilon0∃ϵ0使得f(n)O(nlog⁡ba−ϵ)f(n)O(n^{\log_ba-\epsilon})f(n)O(nlogb​a−ϵ)则T(n)Θ(nlog⁡ba)T(n)\Theta(n^{\log_ba})T(n)Θ(nlogb​a)f(n)f(n)f(n)和nlog⁡ban^{\log_ba}nlogb​a同阶则T(n)Θ(nlog⁡balog⁡n)T(n)\Theta(n^{\log_ba}\log n)T(n)Θ(nlogb​alogn)f(n)f(n)f(n)增速较快若∃ϵ0\exist\epsilon0∃ϵ0使得f(n)Ω(nlog⁡baϵ)f(n)\Omega(n^{\log_ba\epsilon})f(n)Ω(nlogb​aϵ)且af(n/b)≤cf(n)af(n/b)\le cf(n)af(n/b)≤cf(n)则T(n)Θ(f(n))T(n)\Theta(f(n))T(n)Θ(f(n))。无底数log⁡\loglog默认222为底。形式化语言还是太难记了。其实我们将函数f(n)f(n)f(n)与nlog⁡ban^{\log_ba}nlogb​a比较更大的将决定T(n)T(n)T(n)nlog⁡baf(n)n^{\log_ba}f(n)nlogb​af(n)T(n)Θ(nlog⁡ba)T(n)\Theta(n^{\log_ba})T(n)Θ(nlogb​a)nlog⁡baf(n)n^{\log_ba}f(n)nlogb​af(n)T(n)Θ(f(n))T(n)\Theta(f(n))T(n)Θ(f(n))nlog⁡baf(n)n^{\log_ba}f(n)nlogb​af(n)答案乘上对数因子T(n)Θ(nlog⁡balog⁡n)Θ(f(n)log⁡n)T(n)\Theta(n^{\log_ba}\log n)\Theta (f(n)\log n)T(n)Θ(nlogb​alogn)Θ(f(n)logn)。1.T(n)T(n/2)Θ(1)T(n)T(n/2)\Theta(1)T(n)T(n/2)Θ(1)a1,b2a1,b2a1,b2则nlog⁡ban01f(n)n^{\log_ba}n^01f(n)nlogb​an01f(n)所以T(n)Θ(log⁡n)T(n)\Theta(\log n)T(n)Θ(logn)。2.T(n)2T(n/2)Θ(n)T(n)2T(n/2)\Theta(n)T(n)2T(n/2)Θ(n)a2,b2a2,b2a2,b2则nlog⁡ban1nf(n)n^{\log_ba}n^1nf(n)nlogb​an1nf(n)所以T(n)Θ(nlog⁡n)T(n)\Theta(n\log n)T(n)Θ(nlogn)。3.T(n)3T(n/4)Θ(n1.2)T(n)3T(n/4)\Theta(n^{1.2})T(n)3T(n/4)Θ(n1.2)取log⁡430.79\log_430.79log4​30.79a3,b4a3,b4a3,b4则nlogban0.79n1.2n^{log_ba}n^{0.79}n^{1.2}nlogb​an0.79n1.2则T(n)Θ(f(n))Θ(n1.2)T(n)\Theta(f(n))\Theta(n^{1.2})T(n)Θ(f(n))Θ(n1.2)4.T(n)2T(n)Θ(log⁡n)T(n)2T(\sqrt{n})\Theta(\log n)T(n)2T(n​)Θ(logn)有根号比较麻烦我们要想办法把它代换回熟悉的主定理式子。考虑消去根号令mlog⁡nm\log nmlognT(2m)2T(2m/2)Θ(m)T(2^m)2T(2^{m/2})\Theta(m)T(2m)2T(2m/2)Θ(m)把幂取下来不能直接带logloglog进去所以新开个函数H(x)log⁡xH(x)\log xH(x)logxH(m)2H(m/2)Θ(m)H(m)2H(m/2)\Theta(m)H(m)2H(m/2)Θ(m)带入上面主定理mlog⁡22mm^{\log_{2}2}mmlog2​2m所以H(m)Θ(mlog⁡m)H(m)\Theta(m\log m)H(m)Θ(mlogm)代回mlog⁡nm\log nmlognTHΘ(log⁡nlog⁡log⁡n)TH\Theta(\log n\log \log n)THΘ(lognloglogn)