Почему в оценке сложности алгоритма log n пишется без основания?

Question

[mihailos]

Нуу, вопрос сверху
Мне непонятно почему не пишется основание
И какой будет ответ на примере 64?

Comments

[res2001]

Не знаю ответа.
Но я думаю, что основание может быть разным в зависимости от алгоритма.
Например в алгоритме поиска в бинарном дереве основание будет 2, потому что дерево бинарное.
Если бинарное дерево заменить каким-нибудь другим, где из узла могут выходить 3 потомка, то основание будет 3 и т.п.
В оценке не важны конкретные цифры, а важно то, что алгоритм работает с логарифмической сложностью, а не с N или N*N.

И кстати, я иногда встречаю в оценках указание основания логарифма.

Answer 1

[Dalp]

O(n)-это очень примерная оценка сложности алгоритма. В частности она отбрасывает все константы. Из курса алгебры:
log_an = (log_bn)/(log_ba), log_ba-константа и её отбрасывают.
Как видно из этого выражения, основание логарифма в оценке O(n) не имеет смысла.
Однако чаще всего основание-2.

Answer 2

[Лев Забудкин]

Cложность алгоритмов это log N, как Вы пишете без указания основания. Но принято считать, что в таком случае имеется в виду логарифм по основанию 2. В некоторых кругах, но не у нас конечно же, для такого логарифма есть обозначение - lb.

Логарифм 64 по основанию 2 равен 6 (для всех поясню: 2 в 6 степени=64, "логарифм это по сути анти-возведение-в-степень", как мог проще объяснить, так и объяснил)

Comments

[mihailos]

Что такое логарифм я знаю)))
Спасибо за ответ

Answer 3

[dmshar]

В данном контексте выражение log 64 не имеет особого смысла. Сложность алгоритма - это не про то, сколько времени (или памяти) он будет точно занимать, та то, каким образом растет зависимость при n. (См. понятие Асимптотическая сложность алгоритма). Как сказано в других ответах - это весьма примерная оценка, и каково основание логарифма - особой роли не играет. Главное - что она не линейна, не квадратична и пр. а именно "формы графика логарифма". Не больше и не меньше.