Log n как считать

Почему для вычисления сложности алгоритмов используется log N вместо lb N?

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

Отслеживать

задан 6 мар 2018 в 14:52

1,159 9 9 золотых знаков 23 23 серебряных знака 44 44 бронзовых знака

вам будет проще понять если вы построите график отношения log_2(x)/ln(x) и убедитесь, что это константа. Потом прочите ещё раз определение ( f(x) = O(log x) -> 0

Почему в оценке сложности алгоритма log n пишется без основания?

Не знаю ответа.
Но я думаю, что основание может быть разным в зависимости от алгоритма.
Например в алгоритме поиска в бинарном дереве основание будет 2, потому что дерево бинарное.
Если бинарное дерево заменить каким-нибудь другим, где из узла могут выходить 3 потомка, то основание будет 3 и т.п.
В оценке не важны конкретные цифры, а важно то, что алгоритм работает с логарифмической сложностью, а не с N или N*N.

И кстати, я иногда встречаю в оценках указание основания логарифма.

Решения вопроса 2

O(n)-это очень примерная оценка сложности алгоритма. В частности она отбрасывает все константы. Из курса алгебры:
log_an = (log_bn)/(log_ba), log_ba-константа и её отбрасывают.
Как видно из этого выражения, основание логарифма в оценке O(n) не имеет смысла.
Однако чаще всего основание-2.

Ответ написан более трёх лет назад
Комментировать
Нравится 11 Комментировать

Инженер-системотехник, программист, админ, ТПУ.

Cложность алгоритмов это log N, как Вы пишете без указания основания. Но принято считать, что в таком случае имеется в виду логарифм по основанию 2. В некоторых кругах, но не у нас конечно же, для такого логарифма есть обозначение — lb.

Логарифм 64 по основанию 2 равен 6 (для всех поясню: 2 в 6 степени=64, «логарифм это по сути анти-возведение-в-степень», как мог проще объяснить, так и объяснил)

Оценка сложности алгоритмов

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

Для того чтобы обеспечить эффективную работу с такими данными далеко не всегда достаточно реализовать алгоритм, который первым пришел в голову. Зачастую необходимо провести тщательную оценку выбранного алгоритма и выбранной структуры данных, так как в большинстве случаев перед разработчиком ставится выбор между быстродействием алгоритма и объемом используемой памяти. Для этих целей используется специальный подход, о котором далее будет идти речь.

Говоря о сложности алгоритма принято иметь ввиду O-нотацию. Данная нотация имеет свои корни в мат. анализе. Говорят, что неотрицательная функция f(n) не превосходит по порядку функцию g(n) и пишут O(f(n)) = O(g(n)) , если существует такая натуральная константа C, что f (n)

Для наглядности разберем простой пример. Допустим, нам на вход поступает массив строк. Наша задача заключается в том, чтобы вместо каждой строчки записать в этот массив длину этой строчки. Если наш массив будет состоять из 5 ячеек, то эта операция будет занимать 5 у. е. времени. Если же их будет 10, то время будет составлять 10 у. е. Рассуждая таким же способом можно прийти к выводу, что время выполнения нашей задачи линейно зависит от числа элементов этого массива, т. е. от размера входных данных. В таком случае, говорится что время выполнения алгоритма не превосходит O(n), где n – число элементов на входе нашего алгоритма.

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

Первым таким упрощением является то, что мы можем отбросить константы, которые не являются значительными для сравнения. Например, если у нас есть оценка O(n+5), то она эквивалентна O(n). Однако, если нам требуется сравнить O(3n) и O(2n) мы не можем отбросить эти константы и сказать, что алгоритмы эквивалентны с точки зрения времени выполнения. Следующим упрощением является тот факт, что мы в праве оставлять только самую большую по степени функцию для оценки времени. Например, при оценке O(n^3+n^2 +4n) мы можем упростить ее до оценки O(n^3). Следующее упрощение связно с асимптотикой. Чаще всего, когда нам важно оценить скорость работы алгоритма речь идет о больших объемах информации. И здесь нам становится не так важно, поступит ли нам на вход миллион или миллион и одна строка. В таких случаях мы говорим о «худшей» или асимптотической оценке алгоритма. То есть в качестве оценки мы принимаем ту функцию, которая является асимптотой для временной составляющей нашего алгоритма.

Когда мы говорим о ситуациях, в которых мы заранее уверены в некоторой структуре входных данных или в объемах этих данных, можно говорить об оценке снизу и средней оценке. Оценка снизу означает, что мы рассчитываем время, которое потребует наш алгоритм в случае наиболее удачной структуры данных и наиболее удачного порядка данных в этой структуре. Если же мы говорим о средней оценке, то нам достаточно просто сложить оценки сверху и снизу и разделить их пополам.

Наиболее распространёнными оценками являются линейная O(n), логарифмическая O(logn), степенная O(m^n) и экспоненциальная O(e^n), так как она удобна для перехода к операциям с логарифмами. Как показывает практика комбинаций этих сложностей достаточно чтобы оценить большинство алгоритмов.

Давайте рассмотрим данный подход на примере оценки алгоритмов сортировки. Ниже приведен код самой простой сортировки «пузырьком»

for i in range(N-1): for j in range(N-i-1): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j]

Здесь мы видим 2 вложенных цикла. Первый цикл верхнего уровня проходится по элементам от 0 до N-1. Вложенный цикл выполняется N-i-1 раз. Итого оба цикла приблизительно займут N*(N-1)/2 операций. Если вспомнить о том, что мы отбрасываем константы и переменные более низкого порядка получим сложность O(N^2).

Теперь посмотрим на более быстрые алгоритмы сортировки, например, сортировку слиянием. Ниже представлен один из вариантов реализации этого алгоритма.

def merge_sort(nums): if len(nums) > 1: mid = len(nums)//2 left = nums[:mid] right = nums[mid:] merge_sort(left) merge_sort(right) i = j = k = 0 while i < len(left) and j < len(right): if left[i] < right[j]: nums[k] = left[i] i+=1 else: nums[k] = right[j] j+=1 k+=1 while i < len(left): nums[k] = left[i] i+=1 k+=1 while j < len(right): nums[k] = right[j] j+=1 k+=1

В данном алгоритме мы сначала получаем дерево разбиения нашего массива, глубина которого равна log(n). Далее для каждого уровня нашего дерева нам нужно пройтись по n элементам, сравнить их и записать промежуточные результаты. Таким образом сложность данного алгоритма n*log(n). Это в свою очередь быстрее чем рассмотренный ранее алгоритм.

Когда мы оценили несколько алгоритмов с точки зрения времени выполнения, мы можем выбрать алгоритм, который работает быстрее всего. Но в процессе реализации такого алгоритма может возникнуть ситуация, когда для корректной работы необходимо создавать специфические структуры данных, а также дублировать некоторые данные. В этом случае важно оценить, что для нас является более критичным ресурсом — время или память. Чтобы грамотно это оценить необходимо уметь не только выявлять максимальное и минимальное время работы алгоритма, но и оценивать и оптимизировать структуры, в которые мы записываем данные. Приведем пример. Если для какого-либо алгоритма нам необходимо дублировать целочисленный массив, этот алгоритм может показаться нам недостаточно эффективным, даже если он дает прирост в скорости в 1.2 раза. Однако, если мы проведем тщательный анализ данных, оценим возможные значения этих самых данных можно прийти к выводу, что вместо int64 здесь вполне применим int32 или даже int16, что нивелирует необходимость дупликации данных и позволяет использовать более быстрый алгоритм. Но может произойти и более сложная ситуация. Допустим наш алгоритм занимается только операциями поиска вставки и удаления. В голову сразу приходит хэш-таблица, которая позволяет делать все эти операции за константное время. Однако, если мы знаем, что у нас будет не больше 100 элементов нам стоит еще раз подумать о структуре данных, так как операции получения хэша тоже занимают время, а при использовании новых и сложных алгоритмов хэширования, заточенных на избежание коллизий в больших объемах данных это время может быть несоизмеримо больше того времени, которое мы потенциально экономим при использовании этой структуры. Если вернуться к алгоритмам сортировки, рассмотренным ранее, то можно заметить, что сортировка пузырьком работает с исходными данными и не нуждается в дополнительном выделении памяти, тогда как merge sort требует выделение массива такого же размера, как и исходный. Поэтому в данном случае важно понимать какой длины ожидается массив и хватит ли у нас вычислительных ресурсов для его дублирования.

Таким образом, важно помнить, что за двумя зайцами скорее всего угнаться не получится, поэтому важно четко понимать, что для вас обойдется дороже – память или время. А если удалось и ускорить работу алгоритма и использование памяти сократить, лучше на всякий случай перепроверить расчёты.

Log n как считать

Алгоритмы чрезвычайно важны в программировании, потому что вся компьютерная модель функционирует, когда несколько алгоритмов работают вместе. Выбор эффективного решения может быть трудным. Существует различный порядок временной сложности для определения алгоритма, из которых некоторые являются наиболее эффективными, а некоторые — наихудшими.

В блоге студии web-разработки YuSMP Group подробно рассмотрим эту непростую тему.

Что такое анализ сложности

Как определить, эффективна написанная вами программа или нет? Это измеряется сложностью.

Временная сложность алгоритма

В информатике существуют различные задачи и несколько способов решения с использованием разных алгоритмов. Они могут иметь разные подходы, некоторые из них могут быть слишком трудными для реализации, в то время как другие могут решать проблему намного проще. Трудно выбрать подходящий и эффективный вариант из всего имеющегося. Чтобы упростить выбор лучшего алгоритма, важен расчет трудоемкости и времени выполнения. Для этого проводится анализ, который определяет асимптотическую сложность.

Есть три случая, со следующими обозначениями анализа:

• Обозначение Big-oh (O) — верхняя граница времени выполнения, т. е. наихудший сценарий.
• Обозначение Big-omega (Ω) — наилучшее время выполнения.
• Обозначение Big-Theta (Θ) — среднее значение.

Как измерить сложность алгоритмов сортировки

• Константа: если алгоритм выполняется одинаковое количество раз каждый раз, независимо от размера ввода. Говорят, что он демонстрирует постоянную временную сложность.
• Линейный: если время выполнения линейно пропорционально размеру входных данных, то говорят, что алгоритм демонстрирует линейную временную сложность.
• Экспоненциальный: если время выполнения зависит от входного значения, возведенного в степень, то говорят, что алгоритм демонстрирует экспоненциальную временную сложность.
• Логарифмический: когда время выполнения увеличивается очень медленно по сравнению с увеличением размера входных данных, т. е. логарифмически по размеру входных данных, говорят, что алгоритм демонстрирует логарифмическую временную сложность.

Для оценки алгоритмов используется о нотация (Большое-О).

BIG-O	Сложность	Пример
O (1)	Константная	Поиск по ключу в хэш-таблице; арифметическая операция с числом
O (log2 (n))	Логарифмическая	Бинарный поиск, сложность, вставка сбалансированное бинарное дерево
O (n)	Линейная	Поиск перебором; среднеквадратическое отклонение
O (n*log2(n))	Квазилинейное	Самые быстрые алгоритмы сортировки
O (n 2 )	Квадратичная	Простые алгоритмы сортировки; перемножение n-значных чисел «столбиком»
O(n x )	Полиномиальная	LU-разложение матрицы; мощность графа
O (c n )	Экспоненциальная	Задача коммивояжёра (динамическое программирование)
O (n!)	Факториальная	Задача коммивояжёра перебором

Что такое логарифм

Степень, в которую нужно возвести основание, чтобы получить заданное число, называется логарифмом этого числа по соответствующему основанию.

Для нахождения логарифма необходимо знать два фактора: основание и число.

Примеры:

Логарифм 8 по основанию 2 = log 2 (8) = 3
Объяснение: 2 3 = 8

Поскольку 2 нужно возвести в степень 3, чтобы получить 8, таким образом, логарифм 8 по основанию 2 равен 3.

Логарифм 81 по основанию 9 = log 9 (81) = 2,
Объяснение: 9 2 = 81

Поскольку 9 нужно возвести в степень 2, чтобы получить 81, Таким образом, логарифм 81 по основанию 9 равен 2.

Примечание. Экспоненциальная функция является полной противоположностью логарифмической функции. Когда значение многократно умножается, говорят, что оно растет экспоненциально, тогда как когда значение многократно делится, говорят, что оно растет логарифмически.

Что такое О(log n)

O(log N) означает, что время растет линейно, а N растет экспоненциально. Таким образом, если для вычисления 10 элементов требуется 1 секунда, для 100 нужно будет 2 секунды, для 1000 элементов — 3 и так далее.

Бинарный поиск — как раз пример алгоритма. Его структура данных — отсортированный массив из n элементов (что означает n — количество).

Другой пример — быстрая сортировка, когда каждый раз мы делим массив на две части и каждый раз требуется O(N)время, чтобы найти опорный элемент. Следовательно, это N O(log N).

Часто задаваемые вопросы (FAQ) о логарифмической временной сложности:

1) Почему логарифмическая сложность не нуждается в основании?

Логарифмы по любому основанию, т.е. 2, 10, е, можно преобразовать в любое другое основание с добавлением константы, поэтому основание логарифма не имеет значения.

2) Как логарифмы используются в реальной жизни?

В сценариях реальной жизни, таких как измерение кислотного, основного или нейтрального поведения вещества, которое описывает химическое свойство с точки зрения логарифма значения pH.

3) Является ли логарифм повторным делением?

Логарифм — это повторяющееся деление по основанию b до тех пор, пока не будет достигнуто 1. Логарифм — это количество делений на b. Повторное деление не всегда дает ровно 1.

4) В чем разница между логарифмом и алгоритмом?

Алгоритм это пошаговый процесс решения определенной проблемы, тогда как логарифм — показатель степени.

5) Почему бинарный поиск логарифмический?

Двоичный поиск — это метод поиска по принципу «разделяй и властвуй», его ключевая идея — сократить пространство поиска до половины после каждого сравнения для поиска ключа. Таким образом, пространство поиска многократно сокращается вдвое, а сложность становится логарифмической.

6) Что быстрее N или log N?

log N быстрее, чем N, поскольку значение log N меньше, чем N.

7) Что быстрее O(1) или O(log N)?

O (1) быстрее, чем O (log N), поскольку O (1) самая быстрая из возможных.

Вывод

Из приведенного выше обсуждения мы делаем вывод, что анализ очень важен для выбора подходящего алгоритма, а логарифмический порядок является одним из оптимальных порядков сложности по времени.

Эти и другие технологии веб-разработки наши специалисты используют в работе над проектами; примеры можно посмотреть в разделе кейсы YuSMP Group. Если у вас есть идея приложения или другой системы, в реализации помогут веб-услуги и разработка в YuSMP Group. Оставили контакты, чтобы вы могли связаться любым удобным способом.