資結DS 歷屆試題的幾個問題O(n)

看板Grad-ProbAsk作者 (草化)時間10年前 (2015/11/16 23:15), 10年前編輯推噓15(15推 0噓 15→)
留言30則, 8人參與, 最新討論串1/1
1. For 2-3tree an individual rotation or combination operation take O(1) time 這題是交大某一年的， 不過在洪逸應用那本寫True， 在題庫那本寫False 2. (A) log^k(n) = O(n) for any power k. (B) f(n) be a linear function of n , f(n) = Ω log^k(n) for any power k. (C) If k >= 1, then log^k(n) = O(n) 只有C是錯的，想問各位大這類的體型，怎麼判斷 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.7.244 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1447686902.A.C1F.html
推
11/16 23:38, , 1F
1.應該是O(log(n)) 如果是要調整整棵樹的話
11/16 23:38, 1F
→
11/16 23:41, , 2F
2. O的話那應該是答案給錯
11/16 23:41, 2F
→
11/17 00:05, , 3F
所以a也是錯的是嗎
11/17 00:05, 3F
推
11/17 00:11, , 4F
因為要combine兩棵2-3tree還是有可能需要調整
11/17 00:11, 4F
→
11/17 00:11, , 5F
所以既然要調整 就不會是O(1) 所以答案應該是錯的
11/17 00:11, 5F
推
11/17 00:59, , 6F
第二題我會畫線去判斷噎 例如a不管log幾次方 圖形都比O(
11/17 00:59, 6F
→
11/17 00:59, , 7F
n)低 b 因為是線性 所以log一定會更快往t軸靠近 所以是
11/17 00:59, 7F
→
11/17 00:59, , 8F
下限 c當等於1就是反例了
11/17 00:59, 8F
推
11/17 01:03, , 9F
不過如果2-a對 2-c怎麼會錯@@
11/17 01:03, 9F
推
11/17 01:05, , 10F
k=1 log(n) = O(n) 不是反例
11/17 01:05, 10F
推
11/17 01:05, , 11F
2的a跟c到底差在哪?
11/17 01:05, 11F
→
11/17 01:05, , 12F
所以c應該是true
11/17 01:05, 12F
→
11/17 01:06, , 13F
我也覺得很怪 這題c要考應該是考o不是O
11/17 01:06, 13F
→
11/17 01:09, , 14F
嗯嗯 等於1不是反例 說錯了
11/17 01:09, 14F
→
11/17 01:09, , 15F
可是c就算是o答案也是對的不是?
11/17 01:09, 15F
推
11/17 01:09, , 16F
欸對 我想成omega的o了...= =
11/17 01:09, 16F
→
11/17 07:15, , 17F
2. k沒寫constant感覺就算錯 取k=logn
11/17 07:15, 17F
→
11/17 09:34, , 18F
所以log^n(n)大概是多少 必定小於n嗎
11/17 09:34, 18F
可是log(n!)=log(n^n)=nlogn， log^2(n) > log(n^2) 所以理當(logn)^n應該大的些?
→
, , 19F
c選項的話，他題目就給這樣。也是題庫本看到的。
※ 編輯: wanedcol (180.217.6.163), 11/17/2015 10:12:36
推
11/17 23:05, , 20F
第二題很明顯三個都是對的
11/17 23:05, 20F
推
11/17 23:07, , 21F
AC不對 理由就是jerry大說的那樣 logn的logn次就超過線
11/17 23:07, 21F
→
11/17 23:07, , 22F
性等級了
11/17 23:07, 22F
推
11/17 23:09, , 23F
哦但照這樣說B也不對
11/17 23:09, 23F
推
11/17 23:19, , 24F
感覺一般不會考慮k當成任意函數...不過這就是題目瑕疵
11/17 23:19, 24F
→
11/17 23:20, , 25F
log^n(n)與n比較 你兩邊同取log 則nloglogn>logn
11/17 23:20, 25F
推
11/17 23:27, , 26F
抱歉我更正 題目沒有說k是常數 三個都錯
11/17 23:27, 26F
推
11/18 00:01, , 27F
2.c應該是k=1時錯
11/18 00:01, 27F
推
11/18 00:11, , 28F
為什麼k=1時是錯的
11/18 00:11, 28F
我覺得k沒說常數應該只是瑕疵，應該還是要作答，只是k=1跟any power應該是一樣的， 所以三個都對的機率會不會比較高? ※ 編輯: wanedcol (180.217.15.245), 11/18/2015 09:21:06
→
11/18 09:26, , 29F
如果是按照g大的分析，那就是全錯
11/18 09:26, 29F
推
11/18 11:07, , 30F
我搞錯了qq
11/18 11:07, 30F
‣ 更多 wanedcol 的文章
文章代碼(AID): #1MIVBsmV (Grad-ProbAsk)