小弟今天算到一題，怎麼樣也無法得出答案 請各位幫忙
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)