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

[juan19283746 (小阮)]

1. T(n)=4T(n/4)+n/logn

我的解法到最後變成

T(n) = nT(n^1/n)+lognlogn 會變怎樣我也不知道= =

答案給的是 O(nloglogn)


2. T(n)=2T(n^1/2)+logn

答案給的是 O(lognloglogn)


另外問一下 n! = O(n^n) 是最tight的了嗎??


先謝謝了:)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.40.82.208
→ juan19283746:爬文之後都只看到推文說用變數代換的解法
→ juan19283746:但還是不知道如何下手@@
→ juan19283746:然後補充問一下O(2^n)和O(n^logn)哪個大
→ juan19283746:手上的解答是 O(n^logn)大  是我解錯了嗎@@
推 mqazz1:第一題令 m=logn 即可
推 mqazz1:第二題 令m=logn 之後用master解