Чем объяснить переписывание P = 2 ^ (logN) как log2 (P) = log2 (N)?

Question

Я прорабатываю главу Big-O «Взлом кодового интервью» и не могу обернуться вокруг одной из предложенных манипуляций с логарифмами.

Страница 50 книги пытается показать, что O(2<sup>log N</sup>) эквивалентно O(N).

Книга начинается с Let P = 2<sup>log N</sup>, затем она утверждает: «По определению log ₂ мы можем записать это как log ₂ P = log ₂ N "

Это утверждение - то, где мое понимание нарушается. Я не понимаю, как вы можете уменьшить log<sub>2</sub>(2<sup>log N</sup>) до log<sub>2</sub>(N). Если вы посмотрите на график этих двух функций, они явно различаются:

Это шаг к «доказательству» этого N = 2<sup>log N</sup>, что также выглядит как ложное утверждение. Если вы отобразите их снова, N - линейная функция, а 2<sup>log N</sup> - сублинейная функция.

Любые объяснения для начинающих, как это имеет смысл? Спасибо!

---

Изменить, чтобы показать, что log N в этом случае означает log-base-2 (N):

В этом примере из книги log N представляет приблизительную глубину сбалансированного бинарного дерева поиска. Подсчет первых двух слоев дерева дает понять, что мы работаем с log-base-2:

Which log function gives us the answer "Given the number of 
nodes, what is the depth?" Clearly the answer is log-base-2.

  nodes   depth   log2(nodes)   log10(nodes)
      1       1   0             0             
      3       2   1.58          0.48          
      7       3   2.81          0.85          
     15       4   3.91          1.18          
     31       5   4.95          1.49          
     63       6   5.98          1.80          

@ Ответ Кайвена Чена точный. Здесь мы находимся в мире CS, и предполагаемая база журналов равна 2. Книга добавляет эту путаницу, потому что части примера ссылаются на явное log<sub>2</sub>, тогда как log N для описания глубины дерева всегда пишется с предполагаемая база 2.

Answer 1

Это потому, что логарифмические функции являются инверсией экспоненциальных функций , то есть они "отменяют" друг друга .Вы можете думать о логарифмических функциях следующим образом: " На какую силу мне нужно поднять число, чтобы получить другое число ? Что когда вы думаете об этом, предполагая ту же самую базу, звучит многокак экспоненциальная функция. Например,

является логически эквивалентным to: , где основание лог-функции равно 2 .

Таким образом, использование этого знания повышение логарифмической функции в качестве экспоненты экспоненциальной функции приводит к отмене . Таким образом, " отменяет " экспоненциальную. Обратноетакже верно и приведет к тому же результату (то есть журнал показательной функции, с той же самой базой)

Что касается вашего вопроса: Почему O (2 ^ logN)эквивалентно O (N)?

Это потому, что, как отмечено выше, экспоненциальная функция вызывает логарифмическую функцию того же основания, что приводит к отмене, оставляя только N дляостаются. Поэтому результат яs O (N)

Что касается того, почему ваша диаграмма выглядит не очень @Kaiwen Чен дал хорошее объяснение этому расхождению, включая различия в базе.

Надеюсь, это поможет!

Answer 2

В CS многие функции log () предполагаются как основание 2, поэтому 2 ^ (logx) = x. Ваша графическая визуализация предполагает базу 10.

Это общая проблема, с которой сталкиваются студенты-программисты. Все курсы по математике основаны на e, все курсы CS - по основанию 2, а все курсы инженерии - на уровне 10.