O（3^log n）をO（n^log 3）として書き直すことはできますか？

Question

O（3 ^ログn）の複雑さは、O（n ^ログ3）と等しいか、または書き直すことができますか？ここで、対数の底は2

Answer 1

短い答えである：はい

理由は、それが見えるかもしれませとして驚くべきとして、両方の機能は対等であり、単純です。のは、次の表記を使用してみましょう：私たちが知っているように、ln(a^b) = b*ln(a)とlog(x) = ln(x)/ln(2)

：

• ln(x)は自然対数
• log(x)は、ベースにおける対数2

証拠です。我々は両方の機能にこれらの式を適用します。

• ln(3^log(n)) = log(n)*ln(3) = ln(n)*ln(3)/ln(2)
• ln(n^log(3)) = log(3)*ln(n) = ln(3)*ln(n)/ln(2)

両方の機能の対数は等しく、これは両方の機能が同じであることを証明しています。