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

Question

问题在标题中:

我已经收集到了Big-Oh

O(n ³).

因为那将代表多项式的最高程度.最糟糕的情况是时间复杂性.

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

Ω(n ²)

如果是这样的话,我们怎能证明无视第三学位？

谢谢

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.