作者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