2 ^ (log n) = O (log (n))? - PullRequest
Новая
       46

2 ^ (log n) = O (log (n))?

0 голосов
/ 15 сентября 2018

Эти два равны?Я где-то читал, что O (2lg n) = O (n).Исходя из этого наблюдения, я предполагаю, что ответ будет отрицательным, но я не совсем уверен.Буду признателен за любую помощь.

1 Ответ

0 голосов
/ 15 сентября 2018

Во-первых, O(2log(n)) не равно O(n).

Чтобы использовать большие обозначения O, вы найдете функцию, которая представляет сложность вашего алгоритма, а затем вы найдете термин в этой функции с наибольшей скоростью роста.Наконец, вы бы исключили любые постоянные факторы, которые могли бы.

, например, скажем, ваш алгоритм повторяется 4n^2 + 5n + 1 раз, где n - размер ввода.Сначала вы возьмете термин с наивысшей скоростью роста, в данном случае 4n^2, затем удалите все постоянные факторы, оставив сложность O(n^2).

В вашем примере O(2log(n)) можно упростить до O(log(n))

Теперь к вашему вопросу.

В информатике, если не указано иное, обычно можно предположить, что log(n) фактически означает логарифм n, основание 2.

Это означает, что, используя законы логарифма, 2^log(n) может бытьупрощено до O(n)

Доказательство: 

y = 2^log(n)
log(y) = log(2^log(n))
log(y) = log(n) * log(2) [Log(2) = 1 since we are talking about base 2 here]
log(y) = log(n)
y = n
...