Re: [理工] [資結] 時間複雜度
※ 引述《juan19283746 (小阮)》之銘言：
: 1. T(n)=4T(n/4)+n/logn
: 我的解法到最後變成
: T(n) = nT(n^1/n)+lognlogn 會變怎樣我也不知道= =
: 答案給的是 O(nloglogn)
令 m=logn , n=2^m
T(2^m) = 4T( 2^(m-2) ) + (2^m / m)
再令S(m) = T(2^m)
S(m) = 4S(m-2) + (2^m / m)
= 4[ S(m-4) + (2^(m-2) / (m-2)) ] + (2^m / m)
= 4S(m-4) + 2^m/(m-2) + 2^m/m
= ....
= 4S(0) + 2^m/2 + 2^m/4 + ... + 2^m/m
= 2^m( 1/2 + 1/4 + ... + 1/m)
= 2^m(logm)
之後把m換回n的形式
2^(logn) loglogn
n^(log_2_2) loglogn
得到O(nloglogn)
: 2. T(n)=2T(n^1/2)+logn
: 答案給的是 O(lognloglogn)
令m=logn, n=2^m
T(2^m) = 2T(2^(m/2)) + m
再令S(m) = T(2^m)
S(m) = 2S(m/2) + m
套用master method
a=2, b=2, f(m)=m
m^(log_2_2) = m by case2
O(mlogm) = O(lognloglogn)
: 另外問一下 n! = O(n^n) 是最tight的了嗎??
: 先謝謝了:)
至於其他問題我不清楚@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.27.37
推
08/25 20:52, , 1F
08/25 20:52, 1F
推
08/25 21:10, , 2F
08/25 21:10, 2F
推
08/25 23:10, , 3F
08/25 23:10, 3F
→
08/25 23:11, , 4F
08/25 23:11, 4F
→
08/25 23:12, , 5F
08/25 23:12, 5F
→
08/25 23:16, , 6F
08/25 23:16, 6F
→
08/25 23:16, , 7F
08/25 23:16, 7F
討論串 (同標題文章)