Примеры алгоритмов с логарифмической сложностью (основание отличное от 2)

#сложность

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

Ответы

Ответ 1

Ну это просто. Асимптотическая оценка сложности алгоритма O(N) не принимает во внимание
константу перед множителем, тк при больших N она становится несущественной, следовательно
O(N) = C1 * log(N) + C2 записывается как O(N) = log(N)

Известно также, что логарифм с любым основанием можно представить как логарифм по
основанию 2 умноженный на множетель-константу, который по описанной выше причине просто
не учитывается в оценке сложности O(N)


Ответ 2

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

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