Что такое О-большое (Big O notation) ?
Переходя к прочтению информации про алгоритмы, важно понимать, что такое О-большое. Если у вас нет таких знаний, важно прочесть эту статью. Без этих знаний вы не поймете, почему сортировку пузырьком считают не лучшим выбором (как минимум), и статьи по алгоритмам, во многом касающиеся скорости их исполнения, вам будут непонятны.
Итак, что важно для кодера? Как минимум — чтобы его код работал. А на втором месте идет то, как быстро этот код будет работать. Если вы пишете бэкенд для интернет-магазина, покупатели будут не сильно рады, находясь в корзине с покупками, если сайт начнет подвисать. Спасибо за это не скажут точно.
Скорость выполнения кода очень важна! Но как ее оценить? Ведь один и тот же код может выполняться разное время в зависимости от того, на какой машине он запускается. Да даже на одном и том же сервере, в зависимости от его загруженности, код может выполняться разное время. На помощь для оценки скорости выполнения кода приходит О-большое.
О-большое (Big O notation) — это математическая нотация, используемая в программировании для описания асимптотического поведения функций. В контексте алгоритмов она позволяет оценить, как увеличивается время выполнения или потребление памяти алгоритма с ростом размера входных данных.
Говоря понятным языком, О-большое не оценивает скорость выполнения кода в абсолютных величинах (типа секунды, минуты). Чем мощнее машина/сервер, тем быстрее один и тот же код будет выполняться — это очевидно. О-большое — это именно сложность выполнения кода по наихудшему сценарию (о сценариях выполнения — ниже), и оценивает, как при равных технических возможностях будет выполняться код. А именно: сколько понадобится произвести вычислений (выполнить инструкций), чтобы исполнить код.
Пример:
Один кодер написал код, предположим, на 100 строк — инструкции print("что-то"), а второй написал всего 3 строки: два цикла for по 10 итераций и так же print("что-то"). Визуально код первого выглядит громоздким, у второго он элегантен и прост. Но второй код будет выполняться медленнее. Почему? Там столько же инструкций формально, и будет выведено столько же строк на печать, но при каждом переборе цикла тратится время и мощности железа! Каждая отдельная инструкция в первом коде имеет сложность выполнения O(1), а во втором весь код — O(n²). Думаю, тут смысл понятен. О-большое оценивает количество инструкций кода, необходимых для его выполнения по наихудшему сценарию.
Типичные классы сложности О-большого
O(1) — Константная сложность (постоянная сложность)
Время выполнения не зависит от размера входных данных.
Пример: Допустим, у вас есть список с данными (не важно какими). Список может быть любого размера: может быть из одного элемента, а может — из тысяч. Но доступ к элементу списка по индексу (за исключением связных списков, там нужно перебирать, и O — линейное) всегда будет один и тот же.
O(log n) — Логарифмическая сложность
Время растет логарифмически с ростом
n. То есть у нас есть определенное основание, и неважно, какой список: скорость выполнения будет уменьшаться на логарифмическое основание.Пример: бинарный поиск.
O(n) — Линейная сложность
Время растет прямо пропорционально размеру входных данных.
Пример: поиск элемента в неотсортированном массиве. По сути, это простой перебор элементов в последовательности. Вот тут как раз подойдут связные списки — у них именно такая сложность выполнения: чтобы дойти до нужного, нужно перебрать предшествующие.
O(n log n) — Линейно-логарифмическая сложность
Часто встречается в эффективных алгоритмах сортировки.
Пример: сортировка слиянием, быстрая сортировка.
O(n²) — Квадратичная сложность (и иные аналогичные)
Время растет пропорционально квадрату размера входных данных.
Пример: пузырьковая сортировка, сортировка вставками.
Если у нас, допустим, три цикла
for, это уже не квадратичная, а кубическая сложность O(n³).
O(2ⁿ) — Экспоненциальная сложность
Время удваивается с каждым увеличением входных данных.
Пример: решение задачи коммивояжера полным перебором.
Наилучший и наихудший сценарии
Нужно понимать, что О-большое оценивает наихудший сценарий выполнения кода, но на практике все может быть иначе. Поэтому различают:
Наилучший сценарий (например, в линейном поиске — O(1), то есть искомый элемент нашелся сразу).
Наихудший сценарий (то же самое, но O(n), если элемент в самом конце).
То есть можно оценивать как: *"На 100 запусков кода реальная сложность его выполнения будет примерно O(n)/2"* — так как иногда элемент будет находиться сразу, а иногда ближе к концу последовательности.
Важно ли О-большое?
Да, важно. Учитывать сложность выполнения нужно всегда, но в зависимости от задачи этим можно пренебречь, если объем данных, которые будет обрабатывать код, небольшой. В этом случае даже квадратичная сложность (как в пузырьковой сортировке) будет выполняться быстро.
Интересный факт: Даже Python использует несколько алгоритмов сортировки, включая сортировку вставками (в некоторых случаях), а она имеет квадратичную сложность.
Более подробно об этом можно прочитать в книге Кори Альтхофа "Computer Science для программиста-самоучки".