Re: [理工] [演算法] 關於big-O

[peropero1 (嗚嗚~~~~)]

※ 引述《TheJim (TheJim)》之銘言：
: 以下皆為 True or False
: --95 成大資工--
: n^2 + nlogn + n/2 = O(n^8) ------> True
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
O(n^2)必然在O(n^8)內 故本題為true

: --94 交大資訊資結--
: T(n) = 2T(n/2) + n^2 then T(n) = O(n^2logn) ------> False
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
由master theorem  可得T(n)=O(n^2) 故為 False
至於如果這題選true 我想是錯的
因為並不存在常數ε
使得  2logn-ε =  2
     n           n

所以O(n^2) !=Θ(n^2logn), 自然也不等於O(n^2logn)或Ω(n^2logn)

: 這兩題讓我昏頭了
: 有沒有人能解釋一下這兩題的答案
: 為何一個是True 一個是False呢
: P.S 我是看洪逸的資結題庫給的答案
: ------------------------------------------------
: 在加一題
: --93 交大資料資結--
: T(n) = 2T(n/2) + f(n) If f(n) = O(n^2), then T(n) = O(n^2logn) --> False
此題同上 由master theorem可得T(n) = O(n^2)，故為False

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.0.166
※ 編輯: peropero1       來自: 59.126.0.166         (02/11 18:00)
推 boy5548:這題問題不在於是否可以用MASTER METHOD 而是如果是O(n^2)
→ boy5548:就一定也是O(n^2logn)balabala...因為沒說tight bound...
推 SkullMaster:我覺得答案沒什麼問題...
→ SkullMaster:第二題用master theorem得到 T(n)=Θ(n^2)
→ SkullMaster:但Θ(n^2) ≠ O(n^2)
→ SkullMaster:上面打錯 應該是Θ(n^2)≠O(n^2logn)
→ SkullMaster:我是這樣想的...不知道有沒有問題
推 LinkCar:交大要tight  成大不要!!!
→ peropero1:已加入2的想法  一起討論看看
→ boy5548:Θ(n^2) = O(n^2) = O(n^2logn) 那這樣有錯嗎...?
推 SkullMaster:n^2logn = O(n^2logn),但n^2logn≠Θ(n^2)
→ peropero1:skull大 我想原po的問題應該在"n^2是否包含在n^2logn內"
推 SkullMaster:是嗎?@@ 那我誤會了XD
→ peropero1:恩 因為第一題問n^2是否在n^8內
→ aoqq12:其實說不定是洪逸 或者是他助教寫錯了..
→ aoqq12:應該都ture 只要成長速率大於n^2的都可以寫在big-oh內
→ aoqq12:是非題應該是true 如果計算題寫這樣就錯
→ privatewind:同上，不然每題都寫 O(n^n) 超happy
→ sneak: 這題問題不在於是否可以 https://daxiv.com