作者NOtWorThy (分子小於64)
看板Grad-ProbAsk
標題[理工] [DS]-時間複雜度
時間Sun Jan 31 01:14:59 2010
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)
有高手可以解釋一下嗎??
完全看不懂 為何如此
感激不盡~!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.218.120
1F：推 trovadores:用舉例1.n+n^2=theta(n^2) 2.n^2+n^3=omega(n^2) 01/31 01:25
2F：→ tsarnfeng:O(n*n):小於n*n + theta(n*n):等於n*n 複雜度相+後為n*n 01/31 01:25
3F：→ tsarnfeng:以下以此類推 畫圖也很明顯 01/31 01:26
4F：→ trovadores:3. n^2+n^2logn=O(n^2logn) 01/31 01:27
5F：→ NOtWorThy:我覺得若1對 2應該也是要寫theta(n*n)吧?? 模糊了>< 01/31 08:54
6F：→ polomoss:相加取最大...就這樣而已~~之前也問過沒人回 01/31 11:29