作者fish0835 (无用之人)
看板Grad-ProbAsk
标题[理工] [演算法] 演算法的时间复杂度问题
时间Fri Nov 27 12:37:07 2009
想请问一题时间复杂度问题:
题目: 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)
1F：推 FRAXIS:积分的地方有问题.. 11/27 14:50
2F：推 kib65060:积分结果应该是 1 - 1/n , 所以答案是O(n) 11/27 15:18
3F：→ kib65060:上面的1 - 1/n 是指你1 / k^2的积分结果 11/27 15:19
4F：推 doom8199:A(k) 那边我觉得它是 constant time O(1) 11/27 15:28
5F：→ doom8199:因为不论k有多大，一定比 π^2/6 还小 11/27 15:28
6F：→ doom8199:若表示成 O(1/k) , 解释起来会变成 k越大，程式的执行 11/27 15:29
7F：→ doom8199:速度(对A(k)来说) 会越来越快，应该没有这种程式吧 ＝＝ 11/27 15:30
8F：→ doom8199:所以最後应该会推出 T(2^k)=2^k , 即 T(n)=O(n) 11/27 15:33
9F：→ doom8199:比较正确的说明应该是 T(2^k)=2^k*[1 + 1/2^2+...+1/k^2] 11/27 15:40
10F：→ doom8199:然後稍微证明 2^k <= T(2^k) <= (π^2/6)2^k for k>1 11/27 15:41
11F：→ fish0835:我懂了~答案应该是O(n)没错,感谢大家回答唷^_^ 11/27 18:09