complexity-theory - アルゴリズムの複雑さ: log(x^2 + x^3) = O(?)

Question

アルゴリズムの複雑さとプログラミングの対数複雑さの両方の概念を理解していますが、さまざまな累乗の変数を含む対数の複雑さを決定する方法がわかりません。

ここではいくつかの例を示します。

log(x^2 + 3x^3) = O(?)

log(x^3 + 5) = O(?)

どんな助けでも大歓迎です。

ありがとうございました。

Answer 1

O(log(x))

数学的なルールのためだけに（厳密には対数の定義から）log(xk) = k⋅log(x)

また、O は漸近乗法表記であることもわかっているため、定数を掛けても影響はありません。

証拠：

log(x² + 3x³) ≤ log(4x³) ≤ log(x⁴) 十分な大きさの x

したがってlog(x²+3x³) ≤ log(4x³) ≤ log(x⁴) = 4⋅log(x)、私たちが知っているのは、定義により O(log(x)) です

これは、O 境界の上限の証明です。

反対方向 (不要だが興味があるかもしれない Theta を表示)

log(x²+3x³) ≥ log(x²) >= 2⋅log(x)これは、定義により O(log(x)) です