Re: [理工] [資結] 時間複雜度

[mqazz1 (無法顯示)]

※ 引述《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
推 juan19283746:先謝謝了^^  我再研究看看
推 juan19283746:恩  差不多懂了謝啦
推 tureday:n! = O(n^n) 我想是1*2*3*...*（n-1）*n < n*n*n*...*n
→ tureday:=n^n ---> O(n^n)
→ tureday:然後再算lower-bound:1*2*..*（n-1）*n<1*1*..*n/2*..*n/2
→ tureday:其中1乘了n/2個，n/2乘了n/2個 --->Ω(n/2^n/2)=Ω(n^n)
→ tureday:所以最緊密是Θ（n^n)    如果有錯請更正