PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者Sunofgod ( )時間11年前 (2013/11/28 22:33)推噓1(1推 0噓 13→)

留言14則, 5人參與討論串1/1

不知道這邊可不可以請教考試的題目 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

11/28 22:52, , 1^F

11/28 22:52, 1^F

→

suhorng

11/28 22:53, , 2^F

11/28 22:53, 2^F

→

Sunofgod

11/28 22:53, , 3^F

11/28 22:53, 3^F

→

suhorng

11/28 22:54, , 4^F

11/28 22:54, 4^F

→

suhorng

11/28 22:54, , 5^F

11/28 22:54, 5^F

→

suhorng

11/28 22:57, , 6^F

11/28 22:57, 6^F

→

suhorng

11/28 22:57, , 7^F

11/28 22:57, 7^F

→

suhorng

11/28 23:04, , 8^F

11/28 23:04, 8^F

→

suhorng

11/28 23:04, , 9^F

11/28 23:04, 9^F

其實是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

11/29 12:36, , 10^F

11/29 12:36, 10^F

→

Sunofgod

11/29 12:55, , 11^F

11/29 12:55, 11^F

→

Sunofgod

11/29 12:55, , 12^F

11/29 12:55, 12^F