Алгоритмы. Big O

Мы прошли некоторые алгоритмы, в которых встречалось понятие о конкретной сложности алгоритма: O(n), O(n log n) и т.д. На днях я встретил в сети такое видео и решил, что было бы полезно написать пост, в котором описывались бы все эти сложности, и визуально показывалась бы разница между ними. Напомню кратко, о чем речь.

Когда мы пишем код, у нас часто есть несколько способов решить одну и ту же задачу. Для того, чтобы понять, какой из них лучше, можно, конечно, запустить оба варианта и замерить время, но это неудобно: на разных компьютерах результаты будут различаться, а на маленьких объемах данных разница может быть вовсе незаметна. Поэтому в разработке принято использовать другой подход — оценивать, как растет время выполнения алгоритма в зависимости от размера входных данных. Этот инструмент называется нотацией «большое О» (Big O notation). Буква n здесь обозначает размер входных данных: если у вас массив из ста элементов, то n = 100, если из миллиона — n = 1 000 000.

Главная идея Big O заключается в том, что она описывает худший сценарий работы алгоритма и отбрасывает несущественные детали. Нас не интересует точное число операций, важен лишь характер их роста. Поэтому константы отбрасываются (например, 5n превращается в O(n)), а менее значимые слагаемые тоже уходят (так, n² + n становится O(n²)). При очень больших n эти мелкие детали перестают играть роль, и остается только самый быстрорастущий элемент.

Выделяют несколько основных классов сложности.

Константная сложность O(1) означает, что время выполнения не зависит от размера данных: сколько бы элементов ни было, операция всегда занимает одно и то же время. Например, чтобы достать элемент из массива по индексу, компьютеру всё равно, берете ли вы первый или миллионный элемент — он обращается напрямую.

Логарифмическая сложность O(log n) возникает, когда с каждым шагом задачи уменьшаются в несколько раз. Это очень быстрый рост: даже при n = 1 000 000 000 потребуется всего около тридцати шагов. Так работает, например, поиск слова в бумажном словаре: вы открываете его на середине, понимаете, что нужное слово находится во второй половине, отбрасываете первую и повторяете процесс.

Линейная сложность O(n) означает, что время растет пропорционально размеру данных: вдвое больше данных — вдвое больше работы. Типичный пример — поиск конкретного человека в неотсортированной толпе, где придется обойти каждого.

Линейно-логарифмическая сложность O(n log n) чуть хуже линейной, но гораздо лучше квадратичной. В этом классе работают большинство эффективных алгоритмов сортировки, такие как сортировка слиянием (merge sort) или быстрая сортировка (quick sort). Представьте, что вам нужно организовать хаотичную толпу по росту, используя стратегию «делим на группы, сортируем группы, сливаем».

Квадратичная сложность O(n²) означает, что время растет квадратично: при удвоении данных объем работы увеличивается в четыре раза. При n = 1000 это уже миллион операций. Классический пример — вечеринка, где каждый гость должен познакомиться с каждым другим и пожать руку: чем больше гостей, тем непропорционально больше становится рукопожатий. Обычно такая сложность возникает, когда в коде есть цикл внутри цикла, и оба зависят от n.

Экспоненциальная сложность O(2ⁿ) растет еще быстрее: время удваивается с каждым новым элементом. Уже при n = 50 количество операций достигает квадриллиона, поэтому такие алгоритмы на практике применимы только для очень маленьких n. Примером служит перебор всех возможных комбинаций замка с n разрядами.
Самый медленный класс — факториальная сложность O(n!), которая растет катастрофически быстро. При n = 20 количество операций составляет уже 2,4 квинтиллиона. Это характерно, например, для наивного решения задачи коммивояжёра, где нужно найти кратчайший маршрут через n городов полным перебором всех возможных путей.