Re: [理工] [DS]-時間複雜度
※ 引述《NOtWorThy (分子小於64)》之銘言：
: O(n*n) + theta(n*n) = theta(n*n) //最佳表示法
: theta(n*n) + omega(n*n) = omega(n*n)
: theta(n*n) + O(n*n*logn) = O(n*n*logn)
: 有高手可以解釋一下嗎??
: 完全看不懂 為何如此
: 感激不盡~!
我遇到這種題目，都是把上下限分開來看
然後上限和下限分別運算（用集合的角度），最後再把兩者的結果合併
舉例第二題
theta(n*n) + omega(n*n) = ?
上限 O(n*n) + 無界 = 無界
下限 omega(n*n) + omega(n*n) = omega(n*n)
所以答案就是omega(n*n)
第三題
theta(n*n) + O(n*n*logn) =
上限 O(n*n) + O(n*n*logn) = O(n*n*logn)
下限 omega(n*n) + 無界 = omega(n*n)
所以答案是O(n*n*logn) and omega(n*n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
01/31 11:04, , 1F
01/31 11:04, 1F
→
01/31 11:31, , 2F
01/31 11:31, 2F
※ 編輯: FRAXIS 來自: 140.119.162.50 (01/31 18:38)
→
01/31 18:39, , 3F
01/31 18:39, 3F
推
01/31 19:57, , 4F
01/31 19:57, 4F
→
01/31 21:00, , 5F
01/31 21:00, 5F
討論串 (同標題文章)