Почему при оценке сложности алгоритмов через «O» большое и «o» малое никогда не указывают основание логарифмов?

G.A.SH., 441 просмотр

Примечание:
Например, временная сложность двоичного поиска оценивается как O(log(n)).

Примечание:
John Freeman, это понятно. Если бы логарифм имел основание e то писали бы ln, а если 10 то пишут lg. Тут дело в чем-то другом...

Ответы:

John Freeman

Потому что в математике логарифм всегда по дефолту имеет основание e(изредка есть десятичный, но обозначение другое, частенько функции см. ниже имеют абсолютно разные смыслы), это уже в функциях языков итд напихали.

mpiz

На самом деле тут всё из-за свойств O. А именно:
O(a*f(x)) = O(f(x))
А все логарифмы связаны формулой: log(a, x) = log(b,x) / log(b,a), если подставим, то получим:
O(log(a, x)) = O( log(b,x) / log(b,a) ) = O(log(b,x))
Т.е. какое бы ни было основание результат будет одинаковым, а значит это основание можно опустить.

13 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.