小弟今天算到一题，怎么样也无法得出答案 请各位帮忙
T(n) = 2T(n/2) + n*logn 用展开代入法求O(?)
我的算法:
T(n) = 2T(n/2)+ nlogn
代入 T(n/2) = 2T(n/4) + (n/2)log(n/2)
= 2 * [2T(n/4) + (n/2)log(n/2)] + n*log(n)
= 4T(n/4) + n*log(n/2) + n*log(n)
= 4T(n/4) + n*log(n)- 1+ n*log(n)
代入 T(n/4) = 2T(n/4) + (n/4)log(n/4)
= 8T(n/8) + n*log(n) - 2 + n*log(n) - 1 + nlog(n)
= 2^n * T(n/2) + n[logn - 1 + logn -2 +...+ logn -n +log n]
先问为何不能写成 2^n ?
这是我第一个求出来的式子
第二次再算我将 2^n 当成 n(任意数时)
= n * T(n/n) + n [log(n) - 0 + log(n) - 1 + log(n) - 2 +...+log(n) - n ]
= n*log(n) * (n + 1) - n(n + 1) / 2
= n * (log(n)- 1) * (n + 1) /2
可是答案好像是 n * c + n[(1+log(n)) * log(n) / 2]
这之间我哪里算错了??

log(n/2) = log n - log 2 你变成log (n-2)

@@ 请问是哪一段 因为我都是用log(n) -2 除了有几个忘记用()来区别以便方便看之外我看到了 那边是我误打成那样子 但下一段我还是用logn - 1

但你下一行1没乘到n呀n*log(n/2) = n*(log n- log 2)

嗯嗯 了解 我再算算看

叠代到logn项就要终止,因为logn-n是负的,没必要往下算答案是n+n*[(1+logn)*logn]/2 => 0(n(logn)^2)