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