作者asdd (我愛胖穎穎)
看板Examination
標題[考題] 102年關務 資料結構
時間Mon Apr 1 18:50:04 2013
下列哪兩個敘述是錯的
(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+nlog^4 n=O(nlog^4 n)
請問這題大家怎麼選?我個人覺得(D) (E) (F)都錯 可是題目只要兩個.....
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.108.200
※ 編輯: asdd 來自: 114.39.108.200 (04/01 18:53)
1F：推 koyo167:F你是不是抄錯 答案可能是CE 04/01 19:03
2F：推 carterdunk:F是對的 DE錯 04/01 19:08
3F：→ asdd:F怎麼看? 04/01 19:11
4F：推 carterdunk:L'Hospital rule 或取 log 都可以看出 04/01 19:15
5F：推 mhkg:F是對的 n*n < n * log n * log n * logn * logn 04/01 19:28
6F：推 cheng9115053:我覺得先確定n等級是否比(logn)^4大,(F)應該是錯的 04/01 19:34
7F：→ carterdunk:F 題目是n(logn)^4 ? 04/01 19:39
8F：→ carterdunk:如果是 F是錯的 04/01 19:40
9F：→ GLTY:(F)選項的確是3n^2+nlog^4 n=O(nlog^4 n) 04/01 19:43
10F：→ peterchern:我也覺得是CE 04/01 20:19
11F：推 flydragon198:我是選CE C:O(n) E:O(2^n) 不確定對不對 04/01 20:22
12F：推 carterdunk:會選C的人可能要了解O notation的涵義... 04/01 20:23
13F：→ asdd:我是選DE 04/01 20:29
14F：推 haushau:D應該對吧 都是指數時間 只是基底不同而已 04/01 20:30
15F：→ asdd:我的想法是5^n > 2^n*2^n根據定義找不到一個常數c可以滿足 04/01 20:32
16F：→ asdd:c*2^n > 5^n 04/01 20:33
17F：推 leohi:想知道F+1 04/01 20:54
18F：推 mirror520:DF 04/01 21:16
19F：→ link31204:DE一票... 選C的人可能把他當西搭了吧? 04/01 21:20
20F：推 flydragon198:E一定是錯的，100^7 < 1.5^7 ，應該是O(2^n) 04/01 21:20
21F：→ link31204:其實本來不管選那個錯 我第二題都想寫O(N^N)的 .... 04/01 21:25
22F：→ asdd:樓上 XD 你寫了可能很多人會感謝你 04/01 21:27
23F：推 mirror520:1.5^n 感覺成長很小@@ 04/01 21:27
24F：→ asdd:其實 羅必達好像真的蠻好用 只是我個人不太會用@@ 04/01 21:28
25F：→ asdd:不 那是一開始 後續很可怕的!! 04/01 21:29
26F：推 flydragon198:抱歉上面打錯，是1.5^100，不是1.5^7 04/01 21:29
27F：推 mirror520:XD 按了下計算機 有感覺了 感謝 04/01 21:31
28F：→ link31204:寫O(N^N)一定不會錯 只是怕閱卷委員覺得"假行"而已 哈 04/01 21:36
29F：→ asdd:F有沒有人願意分享一下怎樣解的 04/01 23:11
30F：推 wjy123:我這樣看也是覺得DEF都錯耶... :( 04/01 23:27
31F：推 monkeyting:看到推文讓我覺得今年有希望了... 04/02 00:14
32F：→ asdd:所以樓上是寫什麼答案? 04/02 00:21
33F：→ mingrong2:(D)(F)錯誤!! 04/02 00:36
34F：→ mingrong2:(D)5^n>2^n,(F)n^2>nlog^4n 04/02 00:37
35F：→ mingrong2:(E)正確的原因是1.5^n趨近於1,所以等於常數 04/02 00:38
36F：→ mingrong2:n^7+常數=O(n^7) 04/02 00:39
37F：→ mingrong2:原本也差點被他騙><... 04/02 00:40
38F：推 JACKIAM:1.5的50次方就6億多了 怎麼可能趨近於1... 04/02 00:47
39F：→ JACKIAM:只要底數大於1就不可能收斂了... 04/02 00:49
40F：→ mingrong2:對耶!!看錯了= = 04/02 00:50
41F：推 leohi:樓上反串嗎XDDDD 04/02 00:53
42F：推 mingrong2:那不就(D)(E)(F)都錯了= = 04/02 00:54
43F：推 JACKIAM:F的話用lim (n/(logn)^4)作3次羅必達定理會趨近於0 04/02 01:02
44F：→ JACKIAM:所以(logn)^4 比 n大 04/02 01:02
45F：推 leohi:所以可以重複做路邊攤定律 （筆記） 04/02 01:14
46F：推 JACKIAM:不過我剛算錯了~ 後面有人PO正解 可以參考 04/02 01:17
47F：推 davchou:Big O 的定義是緊密上限,不是無限上綱吧 04/02 16:40
48F：→ asdd:根據定義沒錯 你甚至可以寫O(n^n) 更何況他是問對錯? 04/02 17:03
49F：→ asdd:當年在上洪逸的DS老師就有特別拿出來提過 分兩個方向討論 04/02 17:05
50F：→ asdd:一個是根據定義 一個是你說的緊密上限 04/02 17:07
51F：推 wjy123:我朋友說她DEF都選了 因為她怎麼看都覺得錯三個... 04/02 20:58
52F：→ wjy123:題外話 她說她覺得這次她可能會敗在英文跟MIS 04/02 20:59