#алгоритм #математика #сложность
Во всех источниках сложность алгоритмов обозначается как 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
Поскольку все логарифмы одинаковы с точностью до константы :) А так как запись с большим O на константы не реагирует - неважно, какой именно логарифм использовать... Update на ваше обновление вопроса. Смысл не в конкретном количестве сравнений, а в том, как растет это количество (а значит, и время работы) с ростом N. Это ни в коем случае не конкретное количество тех или иных операций! То, что некоторый алгоритм имеет сложность O(g(N)) всего лишь означает, что если мы путем экспериментов будем строить некую функцию зависимости времени работы алгоритма от N и получим некую f(N), то сможем найти некоторые такие константные c и N0, что для всех N>=N0 будет выполняться неравенство 0 <= f(N) <= cg(N). Это - определение записи с большим О. Еще раз - O(N) - это ни в коем случае не количество сравнений, это оценка времени работы алгоритма, максимально отвязанная от деталей реализации и машины. Update2 Я реализую алгоритм бинарного поиска и при этом ужасно туплю, так что вместо одного сравнения я делаю их 20. Вы делаете их ровно столько, сколько нужно. Но и ваша, и моя реализации будут работать время O(log N) - пусть моя и будет работать в 100 раз медленнее вашей. Потому что и моя, и ваша реализации при возрастании N в 100 раз будут работать дольше на некоторое время - пусть и у каждого свое, скажем, у вас на минуту, у меня - на час. Главное, что вид зависимости будет одинаков - при увеличении в сколько-то раз рост будет на сколько-то. И, кстати, у вас зависимости log2x и ln x как раз одинаковы - стоит только немного изменить масштаб по оси y. Что до логарифма по основанию, меньшему 1 - ну, как говорится, не стоит утрировать. Но и тут - достаточно взять его по модулю или отрицательную константу :) А вообще, хватит уже этой переписки - если вас интересует, что такое большое O - то это уже совсем отдельный вопрос... Кстати, вот несколько ссылок отсюда: Введение в анализ сложности алгоритмов (часть 1) Введение в анализ сложности алгоритмов (часть 2) Введение в анализ сложности алгоритмов (часть 3) Введение в анализ сложности алгоритмов (часть 4)Ответ 2
Мне кажется, я нашел ответ на свой изначальный вопрос: "Во всех источниках сложность алгоритмов обозначается как 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." Так что, да, похоже основание логарифма не важно )
Комментариев нет:
Отправить комментарий