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

[wanedcol (草化)]

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
推 goldflower: 1.應該是O(log(n))  如果是要調整整棵樹的話
→ goldflower: 2. O的話那應該是答案給錯
→ wanedcol: 所以a也是錯的是嗎
推 goldflower: 因為要combine兩棵2-3tree還是有可能需要調整
→ goldflower: 所以既然要調整  就不會是O(1)  所以答案應該是錯的
推 yad50968: 第二題我會畫線去判斷噎 例如a不管log幾次方 圖形都比O(
→ yad50968: n)低 b 因為是線性 所以log一定會更快往t軸靠近 所以是
→ yad50968: 下限 c當等於1就是反例了
推 yad50968: 不過如果2-a對 2-c怎麼會錯@@
推 goldflower: k=1 log(n) = O(n)  不是反例
推 JFaker: 2的a跟c到底差在哪?
→ goldflower: 所以c應該是true
→ goldflower: 我也覺得很怪  這題c要考應該是考o不是O
→ yad50968: 嗯嗯 等於1不是反例 說錯了
→ JFaker: 可是c就算是o答案也是對的不是?
推 goldflower: 欸對  我想成omega的o了...= =
→ jerry031181: 2. k沒寫constant感覺就算錯  取k=logn
→ wanedcol: 所以log^n(n)大概是多少 必定小於n嗎
可是log(n!)=log(n^n)=nlogn，
log^2(n) > log(n^2)
所以理當(logn)^n應該大的些?
→ wanedcol: c選項的話，他題目就給這樣。也是題庫本看到的。
※ 編輯: wanedcol (180.217.6.163), 11/17/2015 10:12:36
推 markmushu: 第二題很明顯三個都是對的
推 irenelove: AC不對 理由就是jerry大說的那樣 logn的logn次就超過線
→ irenelove: 性等級了
推 irenelove: 哦但照這樣說B也不對
推 goldflower: 感覺一般不會考慮k當成任意函數...不過這就是題目瑕疵
→ goldflower: log^n(n)與n比較  你兩邊同取log  則nloglogn>logn
推 markmushu: 抱歉我更正 題目沒有說k是常數 三個都錯
推 odanaga: 2.c應該是k=1時錯
推 JFaker: 為什麼k=1時是錯的
我覺得k沒說常數應該只是瑕疵，應該還是要作答，只是k=1跟any power應該是一樣的，
所以三個都對的機率會不會比較高?
※ 編輯: wanedcol (180.217.15.245), 11/18/2015 09:21:06
→ wanedcol: 如果是按照g大的分析，那就是全錯
推 odanaga: 我搞錯了qq