ビッグオメガ表記で17N^2 + 5N^3

Question

質問はタイトルにある：

私はビッグああ

O（nは）であることを集めています。

これは、多項式の最高次数を表します。最悪の場合の時間の複雑さ。

擬似線量により、ビッグオメガ平均最低度？そのような場合にはすなわち

Ω（nは）

は、どのように我々は第三度を無視して正当化することができますか？

ありがとうございました

Answer 1

いいえ、Big-Oは実際には最大の程度は何ですか。ビッグ・オメガは最低の程度は何も言いません。 OとOmegaは、2つの関数を比較すると、実際には1つの関数について何かを言っているのではなく、のツールです。

f = O(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)と言うとき、それはという関数が（定数を無視すると）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の最高度が>=gの最高度であればfの最高度が<=g、およびf = Omega(g)の最高度であれば、それはそのf = O(g)です。