21

Во всех источниках сложность алгоритмов обозначается как 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 произвольное основание потому что зависимость будет совершенно другая - это хорошо видно на графике. Т.о. какой именно логарифм использовать важно. Или я не прав?

1
  • 4
    вам будет проще понять если вы построите график отношения 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 равно).
    – jfs
    7 мар 2018 в 12:42

2 ответа 2

31

Поскольку все логарифмы одинаковы с точностью до константы :)

введите сюда описание изображения

А так как запись с большим O на константы не реагирует - неважно, какой именно логарифм использовать...

Update на ваше обновление вопроса.

Смысл не в конкретном количестве сравнений, а в том, как растет это количество (а значит, и время работы) с ростом N. Это ни в коем случае не конкретное количество тех или иных операций! То, что некоторый алгоритм имеет сложность O(g(N)) всего лишь означает, что если мы путем экспериментов будем строить некую функцию зависимости времени работы алгоритма от N и получим некую f(N), то сможем найти некоторые такие константные c и N0, что для всех N>=N0 будет выполняться неравенство 0 <= f(N) <= cg(N). Это - определение записи с большим О.

Еще раз - O(N) - это ни в коем случае не количество сравнений, это оценка времени работы алгоритма, максимально отвязанная от деталей реализации и машины.

Update 2

Я реализую алгоритм бинарного поиска и при этом ужасно туплю, так что вместо одного сравнения я делаю их 20. Вы делаете их ровно столько, сколько нужно. Но и ваша, и моя реализации будут работать время O(log N) - пусть моя и будет работать в 100 раз медленнее вашей. Потому что и моя, и ваша реализации при возрастании N в 100 раз будут работать дольше на некоторое время - пусть и у каждого свое, скажем, у вас на минуту, у меня - на час. Главное, что вид зависимости будет одинаков - при увеличении в сколько-то раз рост будет на сколько-то.

И, кстати, у вас зависимости log2x и ln x как раз одинаковы - стоит только немного изменить масштаб по оси y. Что до логарифма по основанию, меньшему 1 - ну, как говорится, не стоит утрировать. Но и тут - достаточно взять его по модулю или отрицательную константу :)

Кстати, посмотрите несколько ссылок здесь.

7
  • 1
    О-большое говорит, что для достаточно больших N рост времени работы не быстрее указанной функции (предел отношения меньше константы).
    – jfs
    7 мар 2018 в 12:37
  • @jfs Предел отношения не больше константы. Кстати, определение взято из "Алгоритмов" Кормена и иже с ним.
    – Harry
    7 мар 2018 в 13:04
  • какая разница между "меньше" (<) и "не больше" (<=) если константа не фиксированна? К тому же я не пытался буква в букву определение из какого-то учебника дать, а обозначить как можно думать о big-O (ограничение на рост при большом вводе)
    – jfs
    7 мар 2018 в 13:11
  • 1
    нет, конечно. Это просто значит что отношение меньше бесконечности (ничего не говорит о стремлении к нулю). Подумайте: если у вас: f(x)<=C g(x) для больших x, тогда f(x) < 2C g(x) (увеличили правую положительную часть)¶ Ещё раз: у вас слишком сухой язык и более простой взгляд: «big-O определяет ограничение на рост при большом вводе» — не повредит в качестве комментария к ответу.
    – jfs
    7 мар 2018 в 13:28
  • 1
    Хороший ответ, но я все равно поддерживаю @jfs в разрезе его первого комментария - я хоть и имею, именно, математическое высшее образование, но для краткого ответа использовал бы именно такую формулировку, а затем добавил её детальное пояснение по необходимости, т.к. в него нужно еще вникать (человеку со стороны, не имеющему достаточной мат. базы такое, скорее всего, тяжело дается), а для понимания без углубления в детали (обычно человек именно такого и ожидает) достаточно было именно такого. 20 апр 2018 в 10:05
1

Мне кажется, я нашел ответ на свой изначальный вопрос:

"Во всех источниках сложность алгоритмов обозначается как log N (без указания основания). При этом имеется в виду логарифм по основанию 2. Но для такого логарифма есть свое обозначение lb. Причем это обозначение стандартизировано ISO 31-11 и наверное было бы логичнее и правильнее пользоваться именно им, но этого по какой-то причине не просходит, почему?"

вот здесь: https://en.wikipedia.org/wiki/Logarithm#Particular_bases

т.е. например, в информатике log N используется вместо lb N или log N по конкретному основанию, потому что основание логарифма понятно из контекста.

Возможно, основание логарифма вообще значения не имеет, когда речь идет об О-большое, как ответил @Harry. Но, если честно, моих математических знаний на данный момент не хватает, чтобы дать этому утверждению оценку. Поэтому я предпочту пока более общую формулировку про то, что "основание определено контекстом"

введите сюда описание изображения

UPD: Набрел в одной книг по алгоритмам (как раз в разделе бинарного поиска) на фразу: "Is it log base 2, log base 10, or the natural log? In the above example, log base 2 applies. However, since Big O notation only concerns itself with the shape of the performance the actual base doesn't matter." Так что, да, похоже основание логарифма не важно )

1
  • О-нотация пришла из матанализа, поэтому используется логарифм в математическом смысле - не двоичный, не десятичный, а натуральный, см. «O» большое и «o» малое
    – insolor
    23 фев 2019 в 18:39

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.