big-o - ビッグオーの分類

Question

次の成長を持つ関数があるとします。

2000n^2 + log n

関数が のカテゴリに分類される一連の関数の一部であると結論付けることはできますO(n)か?

Answer 1

O(some function) は、関数の制限動作です。

C * nがすべてのnについて記述した関数の上限を記述するようなCは存在しますか?

関数をよく見ると、C を 2000 に設定して、2000*n^2 = C*n^2...C*n より大きくなるようにすることができます。

いいえ、それは O(n) ではありません。

Answer 2

O(log n) < O(n^x) 固定 x、O(2000n^2 + log(n)) = O(n^2)

これを簡単に確認するには、O(log n) < O(n^x) であるため、O(log n) < O(n^2) であり、O(2000n^2 + log(n)) <= O となります。 (2000n^2 + n^2) = O(2001n^2) = O(n^2) O(2000n^2 + log(n)) には n^2 項があるため、少なくともn^2 は O(2000n^2 + log(n)) >= O(n^2) を与えます。O(2000n^2 + log(n)) <= O(n^2) および O(2000n^2 + log(n)) >= O(n^2) であるため、O( 2000n^2 + log(n)) = O(n^2)