Сложность алгоритма на пальцах: что скрывается за «О-большим»
Почему один поиск находит товар среди миллиона мгновенно, а другой думает минутами? Дело не в мощности компьютера, а в том, как растёт время работы с объёмом данных. Разбираем О-большое без формул и занудства.
О-большое отвечает не на вопрос «как быстро?», а на куда более важный — «как сильно замедлится, когда данных станет вдвое больше?».
Сложность алгоритма описывает скорость роста времени работы при росте объёма данных. Хороший алгоритм на старом ноутбуке легко обгонит плохой на суперкомпьютере — стоит лишь увеличить данные.
Зачем вообще это считать
Представьте два алгоритма поиска. Первый при удвоении данных работает вдвое дольше. Второй при удвоении данных добавляет всего один шаг. На сотне элементов разница незаметна. На миллиарде — первый думает часами, второй отвечает мгновенно. Именно эту разницу в характере роста и ловит О-большое, отбрасывая всё, что зависит от конкретного железа.
Главные классы сложности
Договоримся: $n$ — это количество данных. Вот основные «скорости роста», от лучших к худшим.
O(1) — мгновенно, независимо от объёма
Сколько бы ни было данных, действий всегда одно и то же количество. Пример — взять элемент массива по индексу: arr[5]. Хоть десять элементов, хоть миллиард — одна операция.
O(log n) — почти бесплатно
Каждый шаг отбрасывает половину данных. Это бинарный поиск в отсортированном списке. Чтобы найти слово в миллионе записей, нужно всего около двадцати шагов, ведь $2^{20} \approx 1\,000\,000$. Удвоение данных добавляет один шаг — фантастика.
O(n) — честно и линейно
Просматриваем каждый элемент по разу. Найти максимум в списке, посчитать сумму — это O(n). Вдвое больше данных — вдвое больше работы. Предсказуемо и обычно приемлемо.
O(n log n) — потолок хороших сортировок
Чуть хуже линейной, но всё ещё отлично. Так работают быстрые сортировки (merge sort, быстрая сортировка). Лучше отсортировать произвольные данные нельзя — это доказано.
O(n²) — начинаются проблемы
Для каждого элемента пробегаем все остальные — вложенный цикл. Сравнить каждого с каждым. На 1000 элементов это уже миллион операций. На миллионе — триллион. Такие алгоритмы «взрываются».
Наглядное сравнение
Сколько примерно операций для разных $n$:
| n | O(log n) | O(n) | O(n²) |
| 10 | 3 | 10 | 100 |
| 1 000 | 10 | 1 000 | 1 000 000 |
| 1 000 000 | 20 | 1 000 000 | триллион |
Видно главное: на больших данных разница не в проценты, а в миллионы раз. Никакой апгрейд процессора не спасёт O(n²), если данных по-настоящему много.
Правила чтения О-большого
- Константы отбрасываем. $O(2n)$ — это просто $O(n)$. Нас интересует характер роста, а не множитель.
- Берём худшее слагаемое. $O(n^2 + n)$ — это $O(n^2)$: на больших $n$ квадрат давит линейный член.
- Это про большие данные. На десяти элементах «медленный» алгоритм может быть быстрее «быстрого» из-за накладных расходов. О-большое говорит о тенденции на росте.
Почему это важнее железа
Купить компьютер вдвое быстрее — значит ускорить программу в два раза. Заменить O(n²) на O(n log n) — значит ускорить её в тысячи раз на больших данных. Поэтому опытный инженер сначала смотрит на сложность алгоритма, а уже потом на оптимизацию констант. О-большое — это компас, который заранее говорит, упрётся ли ваш код в стену, когда пользователей станет миллион.