小白问题:根据类似T(N)=T(N/2)+T(2N)+N,这样的表达式,怎样计算时间复杂度?
如题,由于本人非科班毕业,给出这样的表达式,如T(N)=T(N/2)+T(2N)+N,怎么样计算时间复杂度?请各位指点下迷津,说说方法也行了,在百度上实在不知道搜什么关键词!
[解决办法]
这个叫主定理(master theorem),是利用递归树的性质和等比数列推导出来的一个结论,概括起来如下:
T(n) = aT(n/b) + O(n^d)
1、当 d > log b(a)时,开销是O(n^d)。 log b(a)是 b为底a的对数
2、当 d = log b(a)时,开销是O(n^d*log n)
3、当 d < log b(a)时,开销是O(n^log b(a))
但是这个定理只限于右侧只有一个T(n/b)的时候。你写的那个式子是主定理的继续推广,推导过程太复杂,
而且好多数学符号没办法打出来。直接指出来出处,你自己看吧~~
在算法导论第三版的4.5节,推广的证明在 Chapter notes 中给出的