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

看板Grad-ProbAsk作者peropero1 (嗚嗚~~~~)時間15年前 (2011/02/11 17:40)推噓5(5推 0噓 14→)

留言19則, 7人參與討論串2/2 (看更多)

※ 引述《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

02/11 17:47, , 1^F

02/11 17:47, 1^F

→

boy5548

02/11 17:47, , 2^F

02/11 17:47, 2^F

推

SkullMaster

02/11 17:57, , 3^F

02/11 17:57, 3^F