Во всех источниках сложность алгоритмов обозначается как log N (без указания основания). При этом имеется в виду логарифм по основанию 2.
Но для такого логарифма есть свое обозначение lb. Причем это обозначение стандартизировано ISO 31-11 и наверное было бы логичнее и правильнее пользоваться именно им, но этого по какой-то причине не просходит, почему?
UPD: у меня нет никакого математического образования и все, что я знаю о логарифмах, что это действие обратное возведению в степень.
Возьмем конкретный пример - бинарный поиск. Везде описывают его сложность как log N. При этом под log N, как мне кажется, все таки подразумевается логарифм N по основанию именно 2, т.к. количество операций составляет именно логарифм N по основанию 2, т.е. в какую степень надо возвести именно 2 (а не 10 и не 100), чтобы получить N. Поэтому, если честно, я не понимаю ответов типа "потому что постоянные коэффициенты в обозначении O(n) не имеют значения" или "так как запись с большим O на константы не реагирует - неважно, какой именно логарифм использовать..." и буду признателен за более развернутый ответ, написанный не для математиков. Разве правило, что "константы в О-большом не имеют значения", относится к основанию логарифма? Разве для бинарного поиска не имеет никакой разницы как записать его сложность - логарифмом по основанию 2 или по основанию 100?
Если под log N для бинарного поиска подразумевается именно логарифм по основанию 2, то почему бы его не записать как lb N, раз уж для двоичного логарифма есть свое обозначение, вместо того, чтобы записывать вообще без указания основания?
UPD 2: я понимаю что "O(N) - это ни в коем случае не количество сравнений, это оценка времени работы алгоритма, максимально отвязанная от деталей реализации и машины."
Но вот этого: "А так как запись с большим O на константы не реагирует - неважно, какой именно логарифм использовать..." я не понимаю. Почему не важно какой логарифм использовать? Вот графики трех логарифмов - двоичного, натурального и по основанию 0,5:
Возьмем все тот же бинарный поиск. Разве мы можем заменить в его сложности основание у логарифма с два на десять? А с два на 0,5? Мне кажется, не можем. Т.е. мы не можем подставить в выражении log N произвольное основание потому что зависимость будет совершенно другая - это хорошо видно на графике. Т.о. какой именно логарифм использовать важно. Или я не прав?
log_2(x)/ln(x)
и убедитесь, что это константа. Потом прочите ещё раз определение (f(x) = O(log x)
->0 <= f(x) <= C log(x)
для большихx
, гдеC
это константа, которая не зависит отx
). Изменяя основание логарифмы, вы можете значениеC
изменить, но на само соотношениеf(x) = O(log x)
это никак не влияет -- не важно чему C равно).