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

[TheJim (TheJim)]

以下皆為 True or False

--95 成大資工--

n^2 + nlogn + n/2 = O(n^8) ------> True

--94 交大資訊資結--

T(n) = 2T(n/2) + n^2 then T(n) = O(n^2logn) ------> False



這兩題讓我昏頭了

有沒有人能解釋一下這兩題的答案

為何一個是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

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.24.36
推 xup6qup3:第二個是O(n^2)
→ TheJim:那第一題為何不是O(n^2)呢
→ xup6qup3:會不會是因為第二個擺明要你用master method??
推 cakeboy:第二個也對吧,用master method 是 theta(N^2)
→ xup6qup3:對耶 好怪喔XDD
※ 編輯: TheJim          來自: 140.113.24.36        (02/11 11:55)
→ boy5548:會不會是寫成遞迴式通常就要求tight bound...
→ ybite:第一題，因為他是O(n^2)，表示他成長速度比n^2還要慢
→ ybite:因此他成長速度「當然」會比n^8慢，所以也會是O(n^8)
→ ybite:ㄟ等等，我開始懂了問題點
→ ybite:其實如果我，最後兩題我都會選True...
→ sneak: 第二個是O(n^2) https://daxiv.com