作者Sunofgod ( )
看板Prob_Solve
标题[问题] 请教有关时间复杂度的考题
时间Thu Nov 28 22:33:19 2013
不知道这边可不可以请教考试的题目
http://wwwc.moex.gov.tw/ExamQuesFiles/Question/102/102050_13560.pdf
原题在上面
题目节录如下:
Q:下列叙述哪两个是错误
A.0.5n^2+100n=O(n^2)
B.1000=O(1)
C.0.5n+5logn=O(n^2)
D.2n^2+5^n=O(2^n)
E.n^7+1.5^n=O(n^7)
F.3n^2+n(logn)^4=O( n(logn)^4 ) F我这样打应该是对的吧
------------------------------------------------------------
以下是我个人的想法
A跟B没有疑问是对的
C的话应该是在玩定义问题 应该是O(n) 但他写O(n^2)不能说"错"?
D的话我就不大懂了 对5^n取log得到 nlog5 对2^n取log得到nlog2
两者只差常数所以两者成长速度是一样的? 演算法课本都不知道丢掉几年了
如果根本我在胡言乱语请见谅...麻烦请教D的解释
E应该也没疑问O(1.5^n)
F的话我也是用取log的方式判断 对3n^2取log得到log3+2logn
对n(logn)^4取log得到 logn+4log(logn) 所以n(logn)^4成长较快? 所以F是对的?
F也麻烦各位了
根据国考版 当年的给分似乎给得乱七八糟 所以也不管他到底要选几项错误
就单纯讨论各选项到底对或错就好
麻烦各位了~感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.164.88.60
1F：→ suhorng:D为什麽对2^n取log阿? 我看你打 2n^2? 11/28 22:52
2F：→ suhorng:C的确没有错. D即使是2^n跟5^n也不一样,应该是O(5^n) 11/28 22:53
3F：→ Sunofgod:喔喔 我就单纯考虑2^n跟5^n次方而已 记得系数不影响 11/28 22:53
4F：→ suhorng:不可以取log. 回忆定义: f(n)=O(g(n))是 f(n) <= c g(n) 11/28 22:54
5F：→ suhorng:forall n >= n0 11/28 22:54
6F：→ suhorng:log f跟log g只弄出 log(f)<=clog(g), i.e. f <= g^c 11/28 22:57
7F：→ suhorng:无论如何遇到不会的都从 f <= c g 的定义去想 11/28 22:57
8F：→ suhorng:F. lim_{x→∞} xlog^4(x)/x^2 = 0 by l'Hopital rule 11/28 23:04
9F：→ suhorng:因此 n(log^4 n) = O(n^2) //其中一个作法 11/28 23:04
其实是l'Hopital rule忘光了才想到用取log
问人之後懂了 F当n趋近无穷大後会趋近0
同理D可想成lim_{x→∞} 2^x/5^x=lim_{x→∞} (2/5)^x 所以趋近0 因此D是O(5^n)
所以结论 DEF都是错的
感谢你的抽空回答
※ 编辑: Sunofgod 来自: 218.164.88.60 (11/28 23:57)
10F：→ scwg:本版 #1HhBDRyR 有热烈讨论 (?) 11/29 12:36
11F：→ Sunofgod:那篇也是众说纷纭阿 有DE 有DEF 所以我才会想要重问并请 11/29 12:55
12F：→ Sunofgod:帮忙解答的人把想法表达出来 11/29 12:55
13F：→ wsx02:True: A,B,C False: D,E,F 11/29 18:09
14F：推 headking:DEF false 02/02 17:20