Является ли Big log (logn) базой базы?

Для двоичного типа дерева данных типов данных я вижу, что запись Big O обычно обозначается как O (logn). В нижнем регистре «l» в журнале это подразумевает базу данных e (n), как описано натуральным логарифмом? Извините за простой вопрос, но у меня всегда была проблема с разницей между различными подразумеваемыми логарифмами.

    Как только они выражены в примечании Big-O (), оба правильны. Однако при выводе полинома O () в случае двоичного поиска используется только log 2 . Я предполагаю, что это различие было интуитивным вдохновением для вашего вопроса.

    Кроме того, по моему мнению, запись O (log 2 N) лучше для вашего примера, потому что она лучше связывает вывод времени выполнения алгоритма.

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

    Таким образом, O (log N) эквивалентен O (log 2 N) из-за постоянного коэффициента.

    Однако, если вы можете легко набирать log 2 N в свой ответ, то это более педагогично. В случае поиска двоичного дерева вы правы, что log 2 N вводится при выводе времени выполнения Big-O ().

    Прежде чем выразить результат в виде записи большой O (), разница очень важна. При получении полинома, который должен быть передан с помощью записи с большими значениями O, было бы неверным для этого примера использовать логарифм, отличный от log 2 N, до применения O () – обозначения. Как только многочлен используется для передачи наихудшего времени выполнения через запись с большими значениями O (), не имеет значения, какой логарифм используется.

    Значения Big O не зависят от логарифмической базы, поскольку все логарифмы в разных базах связаны постоянным множителем , O(ln n) эквивалентно O(log n) .

    введите описание изображения здесь

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

    Тем не менее, я бы предположил, что лог-база 2.

    Технически база не имеет значения, но вы можете вообще подумать об этом как о базе-2.

    Да, когда речь идет о значении большой О, база не имеет значения. Однако при вычислении, когда речь идет о реальной проблеме поиска, это имеет значение.

    При разработке интуиции о древовидных структурах полезно понять, что двоичное дерево поиска можно искать в O (n log n), потому что это высота дерева, то есть в двоичном дереве с n узлами, дерево глубина – O (n log n) (основание 2). Если каждый узел имеет три дочерних элемента, дерево можно искать в O (n log n), но с логарифмом базы 3. Вычислительно число детей, каждое из которых может иметь большое значение, может иметь большое влияние на производительность (см., Например: текст ссылки )

    Наслаждайтесь!

    Павел

    Оба правильные. Думать об этом

     log2(n)=log(n)/log(2)=O(log(n)) log10(n)=log(n)/log(10)=O(log(n)) logE(n)=log(n)/log(E)=O(log(n)) 

    Сначала вы должны понять, что значит для функции f (n) быть O (g (n)).

    Формальное определение: * Функция f (n) называется O (g (n)), если f | f (n) | <= C * | g (n) | где n> k, где C и k – постоянные. *

    поэтому пусть f (n) = log base a of n, где a> 1 и g (n) = log base b of n, где b> 1

    ПРИМЕЧАНИЕ. Это означает, что значения a и b могут быть любым значением больше 1, например a = 100 и b = 3

    Теперь мы получаем следующее: log base a of n называется O (базовая база b of n), если f | log base a из n | <= C * | база базы b из n | всякий раз, когда n> k

    Выберем k = 0 и C = логарифмическую базу a из b.

    Теперь наше уравнение выглядит следующим образом: | log base a of n | <= базовая база a из базы данных b * | log b of n | всякий раз, когда n> 0

    Обратите внимание на правую сторону, мы можем манипулировать уравнением: = log base a из b * | log base b of n | = | log base b of n | * log base a из b = | log base a из b ^ (база b базы n) | = | log base a из n |

    Теперь наше уравнение выглядит следующим образом: | log base a of n | <= | log base a of n | всякий раз, когда n> 0

    Уравнение всегда истинно независимо от того, какие значения n, b или a есть, кроме их ограничений a, b> 1 и n> 0. Таким образом, логарифмическая база a из n равна O (база базиса b of n), и поскольку a, b не имеет значения, мы можем просто опустить их.

    Вы можете посмотреть видео на YouTube здесь: https://www.youtube.com/watch?v=MY-VCrQCaVw

    Здесь вы можете прочитать статью: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

    Давайте будем гением компьютера.