假设我有以下内容:T(n)= 5n ^ 2 + 2n这是一个非对称的紧密界限是θn^ 2.我想了解放弃5背后的原因.我理解为什么我们忽略低阶条款.
参考big-O的定义.
保持简单[*],如果存在常数C和M,则定义函数g是O(f),使得对于n> M,0 <= g(n)<Cf(n).
f中存在正常数乘数不会影响这一点,只需适当选择C. 您的示例T是O(n ^ 2),通过选择大于5的C值,以及大到足以使其+2n无关的M值.例如,对于n> 2,事实是5n ^ 2 + 2n <6n ^ 2(因为n ^ 2> 2n),因此在C = 6且M = 2的情况下,我们看到T(n)是O(n ^ 2).
所以T(n)确实是O(n ^ 2),并且它也是O(5n ^ 2)和O(5n ^ 2 + 2n).在最有趣的事实是,它是为O(n ^ 2),因为它是最简单的表达,另两个是逻辑上等同.如果我们想比较不同函数的复杂性,那么我们想要使用简单的表达式.
对于big-Theta而言,请注意,当f和g相反时,我们可以发挥相同的技巧.关系"g is Theta(f)"是一个等价关系,那么我们选择什么作为T等价类的代表成员？最简单的一个.
[*]保持事情不那么简单,我们通过使用limsup而不是普通限制来应对负数.我上面的定义实际上已经足够但不是必需的.
| 归档时间： |
|
| 查看次数： |
785 次 |
| 最近记录： |