[問題] 請教有關時間複雜度的考題

[Sunofgod ( )]

不知道這邊可不可以請教考試的題目

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
→ suhorng:D為什麼對2^n取log阿? 我看你打 2n^2?
→ suhorng:C的確沒有錯. D即使是2^n跟5^n也不一樣,應該是O(5^n)
→ Sunofgod:喔喔 我就單純考慮2^n跟5^n次方而已 記得係數不影響
→ suhorng:不可以取log. 回憶定義: f(n)=O(g(n))是 f(n) <= c g(n)
→ suhorng:forall n >= n0
→ suhorng:log f跟log g只弄出 log(f)<=clog(g), i.e. f <= g^c
→ suhorng:無論如何遇到不會的都從 f <= c g 的定義去想
→ suhorng:F. lim_{x→∞} xlog^4(x)/x^2 = 0 by l'Hopital rule
→ suhorng:因此 n(log^4 n) = O(n^2) //其中一個作法
其實是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)
→ scwg:本版 #1HhBDRyR 有熱烈討論 (?)
→ Sunofgod:那篇也是眾說紛紜阿 有DE 有DEF 所以我才會想要重問並請
→ Sunofgod:幫忙解答的人把想法表達出來
→ wsx02:True: A,B,C　　False: D,E,F
推 headking:DEF false