Является ли база журнала Big O (logn) e?

Question 1

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

Question 2

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

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

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

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

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

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

Question 3

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

Question 4

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

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

Question 5

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

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))

Question 6

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

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

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

Павел

Question 7

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

Question 8

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

Формальное определение: * Функция f (n) называется O (g (n)) тогда и только тогда, когда | 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.

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

Выберите k = 0 и C = log base a of b.

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

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

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

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

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

Answer 1

96

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

math binary-tree complexity-theory big-o БакНаполненныйПлатип
источник

58

Как убедительно отмечали другие, это не имеет значения. Все логарифмы отличаются друг от друга константой только в зависимости от используемых оснований. Поскольку эти факторы являются константами, они не имеют значения для целей асимптотического анализа. Во-вторых, что касается определения подразумеваемой базы, это зависит от контекста. В качестве приблизительного практического правила используйте следующее: 1. Когда математик пишет, log nон имеет в виду натуральный логарифм. 2. Когда компьютерный ученый пишет, log nон имеет в виду основание два. 3. Когда инженер пишет, log nон имеет в виду десятичную систему. Обычно это правда.

Джейсон

4

@Jason, еще одно соглашение (в математике) заключается в том, что ln n означает натуральный логарифм, а log n - десятичный. Думайте, что ln означает французское «логарифм naturelle».

Интернет-мужчина

2

Основание логарифма - это количество потомков каждого узла. Если это двоичное дерево, то это журнал с базой 2.

Пол

3

Я ценю твой ответ, Джейсон, и здесь есть над чем подумать. Когда я исследовал, на какой базе находится журнал (я предположил 2), я увидел тот же ответ: это не имеет значения, потому что вы можете исключить константу log_10 (2). Моя проблема с этим заключается в том, что, например: 5 log_10 (5) <5, тогда как 5 log_2 (5)> 5. Я быстро ввел их в свои вычисления, чтобы понять, где O (n logn) имеет лучшее или худшее время выполнения, чем O (п). В зависимости от базы это имеет значение. Поэтому я действительно думаю, что ПРАВИЛЬНЫЙ ответ на этот вопрос должен заключаться в том, что журнал контекстуально означает базу 2 в большинстве компьютерных приложений.

Дуг Мид

@jason, я бы сказал, что проще использовать ln (математическая интерпретация);). Два других примера разумны.

Belford

Answer 2

58

Как убедительно отмечали другие, это не имеет значения. Все логарифмы отличаются друг от друга константой только в зависимости от используемых оснований. Поскольку эти факторы являются константами, они не имеют значения для целей асимптотического анализа. Во-вторых, что касается определения подразумеваемой базы, это зависит от контекста. В качестве приблизительного практического правила используйте следующее: 1. Когда математик пишет, log nон имеет в виду натуральный логарифм. 2. Когда компьютерный ученый пишет, log nон имеет в виду основание два. 3. Когда инженер пишет, log nон имеет в виду десятичную систему. Обычно это правда.

Джейсон

Answer 3

4

@Jason, еще одно соглашение (в математике) заключается в том, что ln n означает натуральный логарифм, а log n - десятичный. Думайте, что ln означает французское «логарифм naturelle».

Интернет-мужчина

Answer 4

2

Основание логарифма - это количество потомков каждого узла. Если это двоичное дерево, то это журнал с базой 2.

Пол

Answer 5

3

Я ценю твой ответ, Джейсон, и здесь есть над чем подумать. Когда я исследовал, на какой базе находится журнал (я предположил 2), я увидел тот же ответ: это не имеет значения, потому что вы можете исключить константу log_10 (2). Моя проблема с этим заключается в том, что, например: 5 log_10 (5) <5, тогда как 5 log_2 (5)> 5. Я быстро ввел их в свои вычисления, чтобы понять, где O (n logn) имеет лучшее или худшее время выполнения, чем O (п). В зависимости от базы это имеет значение. Поэтому я действительно думаю, что ПРАВИЛЬНЫЙ ответ на этот вопрос должен заключаться в том, что журнал контекстуально означает базу 2 в большинстве компьютерных приложений.

Дуг Мид

Answer 6

@jason, я бы сказал, что проще использовать ln (математическая интерпретация);). Два других примера разумны.

Belford

Answer 7

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

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

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

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

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

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

Answer 8

4

Но очень легко показать, что log_2 nэто применимо Θ(log_a n)к любой базе a, поэтому я не уверен, что понимаю, что использование базы 2 «правильнее».

bcat

Answer 9

1

Kinopkio и bcat, спасибо, что помогли им стать полезными. Сначала это было не очень хорошо написано. :)

Хит Ханникатт

Answer 10

2

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

Хит Ханникатт,

Answer 11

11

«при выводе полинома O () в случае двоичного поиска правильным является только log2». -1 за плохую математику. Определение x (n) ~ O (f (n)) говорит, что существует константа c такая, что c * (f (n)) <x (n) для всех n> n_0. Таким образом, постоянный коэффициент не имеет значения при анализе.

rlbond

Answer 12

3

Поскольку log2 (x) равен log10 (x) / log10 (2), вы можете получить его в любом случае. Журнал не является строго основанием 2 в любой момент.

rlbond

Answer 13

80

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

Кейд Ру
источник

2

графика аккуратная, но подумайте о выводе полинома O () ... до применения O () для двоичного поиска подходит только log-base-2.

Хит Ханникатт,

1

@Heath Hunnicutt: Нет. log_2 xОтличается от log_b xпостоянного множителем c(b)для любой базы bнезависимо от x.

Джейсон

4

Но почему вы об этом говорите, когда это не имеет отношения к вопросу и только сбивает с толку?

hobbs

4

Хоббс: Потому что именно этот факт послужил причиной того, что ОП было задумано. Я пытаюсь связать его идеи с ответом, чтобы он понял, почему у него была интуиция, почему она не применима к O (), но не применять то, что он здесь узнает, к выводной части анализа. Краткие ответы, которые не затрагивают основную причину недоразумения, могут привести к дальнейшему недопониманию. Это плохая педагогика.

Хит Ханникатт,

4

@Heath Hunnicutt: Если вы проводите асимптотический анализ, это не имеет значения. То, что вы ждете до последней минуты, чтобы бросить какие-то большие цифры, не меняет того факта, что я могу умножать и делить все свои логарифмы на какую-то глупую константу и изменять базу на всех этапах. То есть, если у меня есть какой-то анализ, который включает log_2 n, я могу просто пойти и заменить log_2 nвезде, log_pi 2 * log_2 n / log_pi 2а затем просто закончить анализом, который есть log_pi 2 * log_pi nвезде. Теперь мой анализ с точки зрения log_pi n.

Джейсон

Answer 14

2

графика аккуратная, но подумайте о выводе полинома O () ... до применения O () для двоичного поиска подходит только log-base-2.

Хит Ханникатт,

Answer 15

1

@Heath Hunnicutt: Нет. log_2 xОтличается от log_b xпостоянного множителем c(b)для любой базы bнезависимо от x.

Джейсон

Answer 16

4

Но почему вы об этом говорите, когда это не имеет отношения к вопросу и только сбивает с толку?

hobbs

Answer 17

4

Хоббс: Потому что именно этот факт послужил причиной того, что ОП было задумано. Я пытаюсь связать его идеи с ответом, чтобы он понял, почему у него была интуиция, почему она не применима к O (), но не применять то, что он здесь узнает, к выводной части анализа. Краткие ответы, которые не затрагивают основную причину недоразумения, могут привести к дальнейшему недопониманию. Это плохая педагогика.

Хит Ханникатт,

Answer 18

4

@Heath Hunnicutt: Если вы проводите асимптотический анализ, это не имеет значения. То, что вы ждете до последней минуты, чтобы бросить какие-то большие цифры, не меняет того факта, что я могу умножать и делить все свои логарифмы на какую-то глупую константу и изменять базу на всех этапах. То есть, если у меня есть какой-то анализ, который включает log_2 n, я могу просто пойти и заменить log_2 nвезде, log_pi 2 * log_2 n / log_pi 2а затем просто закончить анализом, который есть log_pi 2 * log_pi nвезде. Теперь мой анализ с точки зрения log_pi n.

Джейсон

Answer 19

9

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

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

Дэниел Прайден
источник

@Kinopiko: Что именно в этом не так? Точнее, чем мой ответ на самом деле отличается от вашего и других здесь?

Дэниел Прайден,

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

Дэниел Прайден,

Это было моей главной проблемой с вашим ответом. Кроме того, немного неясно, что вы подразумеваете под «они все равно будут иметь какой-то эффект». Некоторое влияние на что?

bcat

1

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

1

@Kinopiko: Хорошо. Я думаю, мы говорим то же самое. Я бы сказал, что O (100) = O (1), потому что O (100) = O (100 * 1) = O (C * 1) = O (1). Именно это я имел в виду, говоря, что постоянные выражения излишни. То есть порядок из любой константы равно 1.

Daniel Pryden

Answer 20

@Kinopiko: Что именно в этом не так? Точнее, чем мой ответ на самом деле отличается от вашего и других здесь?

Дэниел Прайден,

Answer 21

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

Дэниел Прайден,

Answer 22

Это было моей главной проблемой с вашим ответом. Кроме того, немного неясно, что вы подразумеваете под «они все равно будут иметь какой-то эффект». Некоторое влияние на что?

bcat

Answer 23

1

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

Answer 24

1

@Kinopiko: Хорошо. Я думаю, мы говорим то же самое. Я бы сказал, что O (100) = O (1), потому что O (100) = O (100 * 1) = O (C * 1) = O (1). Именно это я имел в виду, говоря, что постоянные выражения излишни. То есть порядок из любой константы равно 1.

Daniel Pryden

Answer 25

7

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

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))

картон
источник

Answer 26

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

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

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

Павел

Answer 27

Вы хотели сказать, что высота двоичного дерева равна log n, а не n log n, верно?

ячейка

Answer 28

1

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

Тим Сильвестр
источник

Answer 29

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

Формальное определение: * Функция f (n) называется O (g (n)) тогда и только тогда, когда | 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.

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

Выберите k = 0 и C = log base a of b.

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

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

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

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

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

Является ли база журнала Big O (logn) e?

Ответы: