作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] [DS]-時間複雜度
時間Sun Jan 31 10:35:54 2010
※ 引述《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
推 wwf90322:請問一下那第一小題怎麼看? O(n*n)+theta(n*n)=O(n*n)? 01/31 11:04
→ polomoss:O+theta = theta 01/31 11:31
※ 編輯: FRAXIS 來自: 140.119.162.50 (01/31 18:38)
→ FRAXIS:第三題寫錯了 修改一下 01/31 18:39
推 NOtWorThy:謝謝你~~!! 那像 O(f(n)) + omega(f(n)) 這種呢 01/31 19:57
→ FRAXIS:變成omega(f(n))吧 我想 01/31 21:00