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

Сложность алгоритмов. Big O. Основы.

Сложность алгоритма — это количественная характеристика, которая говорит о том, сколько времени, либо какой объём памяти потребуется для выполнения алгоритма.

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

Но ведь время выполнения алгоритма зависит от того, на каком устройстве его запустить. Один и тот же алгоритм запущенный на разных устройствах выполняется за разное время.

Тогда было предложено измерять сложность алгоритмов в элементарных шагах — то, сколько действий необходимо совершить для его выполнения. Любой алгоритм включает в себя определённое количество шагов и не важно на каком устройстве он будет запущен, количество шагов останется неизменным. Эту идею принято представлять в виде Big O (или О-нотации).

Big O показывает то, как сложность алгоритма растёт с увеличением входных данных. При этом она всегда показывает худший вариант развития событий — верхнюю границу.

Big O показывает верхнюю границу зависимости между входными параметрами функции и количеством операций, которые выполнит процессор.

Распространённые сложности алгоритмов

Здесь рассмотрены именно распространённые виды, так как рассмотреть все варианты врядли возможно. Всё зависит от алгоритма, который вы оцениваете. Всегда может появится какая-то дополнительная переменная (не константа), которую необходимо будет учесть в функции Big O.

Константная — O(1).

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

Пример № 1.

У нас есть массив из 5 чисел и нам надо получить первый элемент.

val nums = intArrayOf(1, 2, 3, 4, 5) val firstNumber = nums[0]

Насколько возрастет количество операций при увеличении размера входных параметров?
Нинасколько. Даже если массив будет состоять из 100, 1000 или 10 000 элементов нам всеравно потребуется одна операция.

Пример № 2.

Сложение двух чисел. Функция всегда выполняет константное количество операций.

fun pairSum(a: Int, b: Int) = a + b

Пример № 3.

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

fun getSize(nums: List): Int = nums.size

Линейная — O(n).

Означает, что сложность алгоритма линейно растёт с увеличением входных данных. Другими словами, удвоение размера входных данных удвоит и необходимое время для выполнения алгоритма.

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

Пример № 1 — Рекурсивная функция.

1 2 3 4

fun sum(n: Int): Int

Пример № 2 — Линейная функция.

1 2 3 4 5 6 7 8 9

fun pairSumSequence(n: Int): Int < var sum = 0 for (i in 0 until n) < sum += pairSum(i, i + 1) >return sum > fun pairSum(a: Int, b: Int) = a + b

Функция pairSumSequence() в цикле складывает какие-либо пары чисел, вызывая функцию pairSum() . Цикл выполняется от 0 до n. Т.е. чем больше n, тем больше раз выполнится цикл. Поэтому сложность функции pairSumSequence() — O(n).

Пример № 3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

fun sum(nums: List) < var sum = 0 var product = 1 for(num in nums) < sum += num >for(num in nums) < product *= num >println(sum, product) >

В функции два последовательных цикла for , каждый из которых проходит массив длиной n, следовательно сложность будет: O(n + n) = O(n)

Логарифмическая — O(log n).

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

К алгоритмам с такой сложностью относятся алгоритмы типа “Разделяй и Властвуй” (Divide and Conquer), например бинарный поиск.

Линеарифметическая или линеаризованная — O(n * log n).

Означает, что удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое.

Примеры алгоритмов с такой сложностью: Сортировка слиянием или множеством n элементов.

Квадратичная — O(n 2 ), O(n^2).

Означает, что удвоение размера входных данных увеличивает время выполнения в 4 раза. Например, при увеличении данных в 10 раз, количество операций (и время выполнения) увеличится примерно в 100 раз. Если алгоритм имеет квадратичную сложность, то это повод пересмотреть необходимость использования данного алгоритма. Но иногда этого не избежать.

Такие алгоритмы легко узнать по вложенным циклам.

Пример № 1.

1 2 3 4 5 6 7

fun printPairs(nums: List > >

В функции есть цикл в цикле, каждый из них проходит массив длиной n, следовательно сложность будет: O(n * n) = O(n 2 )

Зачем изучать Big O

• Концепцию Big O необходимо понимать, чтобы уметь видеть и исправлять неоптимальный код.
• Ни один серьёзный проект, как ни одно серьёзное собеседование, не могут обойтись без вопросов о Big O.
• Непонимание Big O ведёт к серьёзной потере производительности ваших алгоритмов.

Шпаргалка

Небольшие подсказки, которые помогут определить сложность алгоритма.

• Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1).
• Перебор коллекции это O(n).
• Вложенные циклы по той же коллекции это O(n 2 ).
• Разделяй и властвуй (Divide and Conquer) всегда O(log n).
• Итерации которые используют “Разделяй и властвуй” (Divide and Conquer) это O(n log n).

Полезные ссылки

Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О — 25-минутное видео, в котором очень доступно (и с примерами) объясняются основы анализа сложности алгоритмов.
Big O — статья на хабре о Big O.
Знай сложности алгоритмов — статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов.

Почему в оценке сложности алгоритма 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, «логарифм это по сути анти-возведение-в-степень», как мог проще объяснить, так и объяснил)

Почему для вычисления сложности алгоритмов используется 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 как считать

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

В блоге студии 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. Оставили контакты, чтобы вы могли связаться любым удобным способом.