Как упростить O (2 ^ (logN)) до O (N)

Question

В Cracking the Coding Interview есть пример, где время выполнения для рекурсивного алгоритма, который подсчитывает узлы в двоичном дереве поиска, равно O (2 ^ (logN)). Книга объясняет, как мы упрощаем, чтобы получить O (N) так ...

2^p = Q 
logQ = P 
Let P = 2^(logN).

но я заблудился на этапе, когда они говорят: «Пусть P = 2 ^ (logN)». Я не понимаю, как мы знаем, чтобы установить эти два равными друг другу, и я также не понимаю этот следующий шаг ... (Хотя они говорят мне, что они делают это по определению базы журнала 2)

logP = logN 
P = N 
2^(logN) = N

Следовательно, время выполнения кода равно O (N)

Answer 1

Определение логарифма: «до какой степени нужно поднять основание, чтобы получить это значение», поэтому, если основание логарифма равно 2, то повышение 2 до этой степени возвращает нас к исходному значению.

Пример: N равно 256. Если мы возьмем логарифм с основанием 2, мы получим 8. Если мы возведем 2 в степень 8, мы получим 256. Таким образом, оно является линейным, и мы можем сделать его равным просто N.

Если журнал будет находиться в другой базе, например, 10, преобразование просто потребует деления показателя степени на константу, делая более точную форму в N = 2^(log N / log 2), которую можно изменить в N / 2^(1 / log 2) = 2^log N. Здесь делитель для N слева является константой, поэтому мы можем забыть об этом при обсуждении сложности и снова прийти к N = 2^log N.

Вы также можете проверить это вручную. Log2 из 256 - 8. Log2 из 128 - 7. 8/7 - около 1,14. Log10 из 256 составляет 2,4. Log10 из 128 составляет 2,1. 2,4 / 2,1 составляет около 1,14. Таким образом, база не имеет значения, ценность, которую вы получаете, не одинакова, но она линейна. Математически N не равно 2 ^ Log10 N, но в терминах сложности это так.

Answer 2

Короткий ответ заключается в том, что исходный вопрос, вероятно, неявно предполагал, что логарифм должен быть в базе 2, так что 2 ^ (log_2 (N)) - это просто N, по определению log_2 (x) как обратной функции из 2 ^ лет

Тем не менее, интересно исследовать это немного более тщательно, если логарифм относится к другой базе. Стандартные результаты позволяют записать логарифм в основание b следующим образом:

, где ln(x) - натуральный логарифм (используется основание e). Точно так же можно переписать 2^x следующим образом:

Затем мы можем переписать исходное выражение порядка следующим образом:

, которое можно уменьшить до:

Итак, если основание b нашего логарифма равно 2, то это явно просто N. Однако, если база отличается, мы получаем N, возведенное в степень. Например, если b=10, мы возводим N в степень 0,301, что, безусловно, является медленнее возрастающей функцией, чем O(N).

Мы можем проверить это напрямую с помощью следующего скрипта Python:

import numpy
import matplotlib.pyplot as plt

N = numpy.arange(1, 100)

plt.figure()
plt.plot(N, 2**(numpy.log2(N)))
plt.xlabel('N')
plt.ylabel(r'$2^{\log_2 N}$')

plt.figure()
plt.plot(N, 2**(numpy.log10(N)))
plt.xlabel('N')
plt.ylabel(r'$2^{\log_{10} N}$')

plt.show()

График, который получается, когда мы предполагаем, что логарифм основывается на двух:

сильно отличается от графика, когда логарифм принимается за основание десять:

Answer 3

^{Предполагая, что logN - это лог ₂ N}

Эта строка:

Let P = 2^(logN).

Просто предполагает, что P равно 2^(logN).Вы еще не знаете N, вы просто определяете, как P и N связаны друг с другом.

Позже вы можете применить функцию log к обеим сторонам уравнения.И поскольку log(2^(logN)) равно logN, следующим шагом будет:

logP = logN

И, очевидно, когда logP = logN, то:

P = N

И ранее вы предполагали, что P = 2^(logN), затем:

2^(logN) = N

Более того, все это можно упростить до 2^logN = N путем определения функции log.