[理工] [演算法] 演算法的時間複雜度問題

[fish0835 (無用之人)]

想請問一題時間複雜度問題:

題目: 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)
推 FRAXIS:積分的地方有問題..
推 kib65060:積分結果應該是 1 - 1/n , 所以答案是O(n)
→ kib65060:上面的1 - 1/n 是指你1 / k^2的積分結果
推 doom8199:A(k) 那邊我覺得它是 constant time  O(1)
→ doom8199:因為不論k有多大，一定比  π^2/6 還小
→ doom8199:若表示成 O(1/k) , 解釋起來會變成 k越大，程式的執行
→ doom8199:速度(對A(k)來說) 會越來越快，應該沒有這種程式吧　＝＝
→ doom8199:所以最後應該會推出 T(2^k)=2^k , 即 T(n)=O(n)
→ doom8199:比較正確的說明應該是 T(2^k)=2^k*[1 + 1/2^2+...+1/k^2]
→ doom8199:然後稍微證明  2^k <= T(2^k) <= (π^2/6)2^k  for k>1
→ fish0835:我懂了~答案應該是O(n)沒錯,感謝大家回答唷^_^