作者assassin88 (2010)
看板Grad-ProbAsk
標題[理工] [algo]-求解複雜度
時間Sat Jan 23 23:41:28 2010
一、 1.1 1.1
f(n) = n g(n) = n(logn)
我是取 log(f(n)) = 1.1logn
1.1
log(g(n)) = log{ n(logn) } = logn + 1.1loglogn
f(n) = Θ(g(n))，這樣有算錯嗎？
因為題目是用 lim 求的，求出來為0，是 f(n) = Ω(g(n))，麻煩指導一下。
二、f(n) = n + n/2 + n/4 + ... + 1 = n(logn)
g(n) = n + 2n/2 + 3n/4 + ... + (lnn) = ？
不知道f(n)有沒有求錯，請問 f(n) = ？(g(n))~~~感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.104.12
1F：推 FRAXIS:第一題取log來判斷複雜度的地方有問題.. 01/23 23:50
2F：→ FRAXIS:第二題f是O(n), g我看不出來你要表達的級數是什麼.. 01/23 23:50
3F：→ assassin88:請問第一題是..？ 01/24 00:05
4F：→ assassin88:g是因為我求不出來= = 噢f(n)算錯.. 01/24 00:06
5F：推 polomoss:第一題f(n)=Omega(g(n)) 01/24 00:29
6F：→ assassin88:請問第一題的g(n)是等於 logn+1.1logn嗎？ 01/24 16:06
7F：→ assassin88:這樣不是Θ？ 01/24 16:06
8F：→ polomoss:不能這樣看，你把兩邊的n^1去掉，再取log就知道為何了 01/24 20:08
9F：→ polomoss:左邊剩下n^0.1右邊為logn^k取log完左邊大 01/24 20:09
10F：→ assassin88:原來如此~我懂了Orz.. 01/24 21:32