可以将O(3 ^ log n)重写为O(n ^ log 3)吗？

Question

O(3 ^{log n})的时间复杂度是否等于或重写为O(n ^{log 3})？这里,对数基数为2.

Answer 1

简短回答:是的

原因很简单,尽管它看起来很令人惊讶,但两个函数都是平等的.我们使用以下符号:

• ln(x) 是自然对数
• log(x) 是基数2的对数

证据:

我们知道,ln(a^b) = b*ln(a)和log(x) = ln(x)/ln(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)

两个函数的对数相等,这证明两个函数是相等的.