Биг-О запись 8 ^ log2 (n)

Question

Меня смущает, что будет означать биг-О 8^(log2(n)).

Вы бы просто смогли изменить его на O(8^n), поскольку log2 в некоторой степени будет действовать как константа, которая просто уменьшает значение n? или это будет что-то еще?

В чем-то похожем случае, что будет биг-О для log2(n^n). это будет просто O(log2(n))?

Answer 1

Нам понадобятся следующие свойства журналов и показателей, чтобы понять это:

1. b ^{Log _b (x)} = x

2. k. Log _b (x) = Log _b (x ^k )

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

---

Для первой задачи:

8 ^{Log ₂ (n)}

= (2 ³ ) ^{Log ₂ (n)} (потому что 8 = 2 ³ )

= 2 ^{3. Log ₂ (n)} (с использованием Prop # 3)

= 2 ^{Log ₂ (n 3 )} (с использованием проп. 2)

= n ³ (с использованием проп. 1)

= O (n ³ )

---

Для второй задачи:

Log ₂ (n ⁿ )

= n. Log ₂ (n) (с использованием Prop # 2)

= O (n Log (n))

Answer 2

Big-O 8^(log(n)) будет O(2^log(n)) как 8 = 2^3.

Также log(n^n) = n*log(n). Так что big-O for log2(n^n) будет O(n*log2(n))