主题:请教一个算法复杂度问题
sunseed
[专家分:20] 发布于 2007-03-19 22:18:00
递归定义
T(n)= O(1) , n <= 1;
2T(n/2) +O(n); n >1
T (n) = O()???
请教```
回复列表 (共1个回复)
沙发
sunseed [专家分:20] 发布于 2007-03-19 22:51:00
找到了
T(n)=2*T(n/2) + O(n)
=4*T(n/4) + 2*O(n/2) + O(n)
=4*T(n/4) + 2*O(n)
=8*T(n/8) + 3*O(n)
...
=2^k * T(n/ 2^k) + k*O(n)
令 (n/2^k)=1, k=log(n) (注:log(n)是以2为底)
则原式T(n)等于
=n*T(1) + log(n) * O(n)
=n*O(1) + O(n*log(n))
=O(n) + O(n*log(n))
=O(n*log(n))
我来回复