Обозначение Big O Log Base 2 или Log Base 10

Когда в статьях/вопросах говорится, что время работы алгоритма Big O равно O(LogN) .

Например, Quicksort имеет время работы Big O, равное O (LogN), где это логарифмическая база 10, но высота двоичного дерева равна O (LogN + 1), где это логарифмическая база 2.

Вопрос

1) Меня смущает, является ли это основанием журнала 10 или основанием журнала 2, поскольку в разных статьях используются разные основания для их логарифма.

2) Имеет ли значение, если его логарифмическая база 2 или логарифмическая база 10??

3) Можем ли мы предположить, что это означает логарифмическую базу 10, когда мы видим O (LogN) ???


algorithm big-o logarithm
person Computernerd    schedule 20.12.2013    source источник
comment
Обычно учебники и академические статьи подразумевают log_2 n, когда говорят log n. Это легче всего понять, если рассмотреть один из самых первых алгоритмов, обсуждавшихся в классах сложности: бинарный поиск. Вся предпосылка бинарного поиска заключается в том, что он сокращает вашу работу на половину на каждом шаге, поэтому сложность алгоритма составляет именно log_2 n. Хотя любая постоянная база может быть допустима при использовании нотации big-O, всегда полезно подумать о том, почему сложность является логарифмической. Это потому, что каждый шаг сокращает вашу работу вдвое? К десяти?   -  person dg99    schedule 20.12.2013
comment
Зависит от того, сколько способов ваша стадия принятия решений дает за итерацию в вашем алгоритме. Если это 2, например, проверьте условие и либо сделайте это, либо сделайте то, то это основание 2, но если вы принимаете решение с тремя результатами, чем основание 3 и так далее. Люди говорят, что база не имеет значения, но она имеет значение, например, когда вам нужно вычислить n Log(n).   -  person Redu    schedule 23.02.2017

Ответы (3)


arrow_upward
49
arrow_downward

Я думаю, что не имеет значения, что является основой журнала, поскольку относительная сложность одинакова независимо от используемой базы.

Таким образом, вы можете представить это как O(log2X) = O(log10X)

Также упомянуть, что логарифмы связаны некоторой константой.

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

So

log₁₀(x) = log₂(x) / log₂(10)

Поэтому большую часть времени мы обычно игнорируем константы в анализе сложности, и поэтому мы говорим, что основание не имеет значения.

Также вы можете обнаружить, что в большинстве случаев основание считается равным 2, как в сортировке слиянием. Дерево имеет высоту log₂ n, так как узел имеет две ветви.

1) Меня смущает, является ли это основанием журнала 10 или основанием журнала 2, поскольку в разных статьях используются разные основания для их логарифма.

Итак, как объяснялось выше, это изменение базы не имеет значения.

2) Имеет ли значение, если его логарифмическая база 2 или логарифмическая база 10??

Нет, это не имеет значения.

3) Можем ли мы предположить, что это означает логарифмическую базу 10, когда мы видим O (LogN) ???

Да, вы можете предположить это, если знаете базовое правило преобразования.

person Rahul Tripathi    schedule 20.12.2013
comment
Что ж, это верно только в том случае, если основание журнала является константой. log_2 n похож на log_10 n, но не на log_n n. :) - person dg99; 20.12.2013
comment
@ dg99: - Я обновил свой ответ. Надеюсь, так будет понятнее :) - person Rahul Tripathi; 20.12.2013

arrow_upward
16
arrow_downward

log₁₀(x) = log₂(x) / log₂(10) для всех x. 1/log₂(10) — постоянный множитель, который можно исключить из асимптотического анализа.

В более общем случае основание любого логарифма можно изменить с a на b (оба константы относительно n) путем деления на logₐ(b), поэтому вы можете свободно переключаться между базами журнала больше единицы: O(log₁₀(n)) равно O(log₂(n )), O(ln(n)) и т. д.

Примером следствия этого является то, что B-деревья асимптотически не превосходят сбалансированные бинарные деревья поиска. , даже несмотря на то, что они дают более высокие логарифмические основания при анализе. Просто у них лучше константы.

person Fred Foo    schedule 20.12.2013

arrow_upward
9
arrow_downward

В нотации Big O O(log(n)) одинаково для всех оснований. Это связано с преобразованием основания логарифма:

log2(n) = log10(n)/log10(2)

1/log10(2) — это просто постоянный множитель, поэтому O(log2(n)) совпадает с O(log10(n)).

person dkrikun    schedule 20.12.2013