performance - Big-Omega 表示法中的 17n^2+5n^3

Question

问题在标题中:

我猜到 Big-Oh 是

O(n³).

因为那将代表多项式的最高阶。以及最坏情况下的时间复杂度。

通过限制剂量 Big-Omega 意味着最低程度？即

Ω(n²)

如果是这样，我们如何证明无视 3 度是合理的？

谢谢

Answer 1

没有。 Big-O并没有真正说明最大程度是什么；这只是一个快速规则——Big-Omega 并没有说明最低度数是多少。 O和 Omega是真正用于比较两个函数的工具，而不是用于说明一个函数的东西。

当我们说 f = O(g) , 这意味着函数 f增长速度不超过 g (当忽略常数因素时)。所以17n^2 + 5n^3 = O(n^3) ，但情况也是如此 17n^2 + 5n^3 = O(n^4) , 17n^2 + 5n^3 = O(n^5) , 和 17n^2 + 5n^3 = O(18036523n^38576) - 但事实并非如此 17n^2 + 5n^3 = O(n^2.9999999) .

当我们说 f = Omega(g) , 这意味着函数 f不会比 g 慢(当忽略常数因素时)。所以17n^2 + 5n^3 = Omega(n^3) , 和 17n^2 + 5n^3 = O(n^2) , 和 17n^2 + 5n^3 = O(n) , 和 17n^2 + 5n^3 = O(1) ，但事实并非如此 17n^2 + 5n^3 = O(n^3.000001) .

所以如果你想要一个快速的规则，那就是 f = O(g)如果最高学历f是<=最高学历g , 和 f = Omega(g)如果最高学历f是>=最高学历g .