[理工] [演算法]-想問一題時間複雜度問題
想請問一題時間複雜度問題:
題目: T(n) = 2T(n/2) + n / (lgn)^2 的時間複雜度是多少?
我的算法:
k
n = 2 代入
k k-1 k 2
=> T(2 ) = 2T(2 ) + 2 / k
k k k-1 k-1 2
=> 1/2 T(2 ) = 1/2 T(2 ) + 1/k
k k
令A(k) = 1/2 T(2 )
2 2 2 2
=> A(k) = A(k-1) + 1/k = 1 + 1/2 + 1/3 + ... + 1/k (對他作積分)
-1 k k
= O( k ) = 1/2 T(2 )
k k
=> T(2 ) = O( 2 /k )
=> T(n) = O( n / lgn)
但是答案被助教劃掉，不知道有沒有人知道問題在哪裡...
--
請勿嘗試 "複製 -> 貼上" 紫色區塊唷！
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqg
y
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.214.45
※ 編輯: fish0835 來自: 140.113.214.45 (11/27 12:37)
推
11/27 14:50, , 1F
11/27 14:50, 1F
推
11/27 15:18, , 2F
11/27 15:18, 2F
→
11/27 15:19, , 3F
11/27 15:19, 3F
推
11/27 15:28, , 4F
11/27 15:28, 4F
→
11/27 15:28, , 5F
11/27 15:28, 5F
→
11/27 15:29, , 6F
11/27 15:29, 6F
→
11/27 15:30, , 7F
11/27 15:30, 7F
→
11/27 15:33, , 8F
11/27 15:33, 8F
→
11/27 15:40, , 9F
11/27 15:40, 9F
→
11/27 15:41, , 10F
11/27 15:41, 10F
→
11/27 18:09, , 11F
11/27 18:09, 11F