[考題] 102年關務 資料結構

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