作者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