Ответ 1

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

Итак, вы можете думать о нем как о (log ₂ X) = O (log ₁₀ X)

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

Итак,

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

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

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

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

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

2) Имеет ли значение значение, если его база 2 базы или база 10?

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

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

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

Ответ 2

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-tree не разбивают сбалансированные бинарные деревья поиска асимптотически, хотя они дают более высокие базисные базы в анализ. Просто имеют лучшие константы.

Ответ 3

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

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

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