8^log2(n) 的大 O 表示法

Question

我对 8^(log2(n)) 的大 O 表示法感到困惑。

您能否将其更改为 O(8^n)，因为 log2 会在某种程度上充当常数，只会减少 n 的值？还是别的东西？

在有点类似的情况下，log2(n^n) 的大 O 是什么。这只是 O(log2(n)) 吗？

Answer 1

8^(log(n)) 的大 O 将 O(2^log(n)) 为 8 = 2^3。

还有log(n^n) = n*log(n)。所以 big-O for log2(n^n) 会是 O(n*log2(n))

Answer 2

我们需要以下对数和指数的属性来理解这一点：

1. b^Log_b(x) = x

2. k . Log_b(x) = Log_b(x^k)

3. (x^a)^b = x^a.b

---

第一个问题：

8^Log₂(n)

= (2³)^Log₂(n) (because 8 = 2³)

= 2^{3 . Log₂(n)} (using Prop#3)

= 2^Log₂(n3) (using Prop#2)

= n³ (using Prop#1)

= O(n³)

---

对于第二个问题：

Log₂(nⁿ)

= n . Log₂(n) (using Prop#2)

= O(n Log(n))