Сложность алгоритма показывает, как растёт время работы с ростом данных. Её оценка через O-большое позволяет заранее понять, справится ли программа с миллионом элементов и какую сортировку выбрать.
Что нужно знать
- Порядки роста: $O(1)$ < $O(\log n)$ < $O(n)$ < $O(n \log n)$ < $O(n^2)$.
- Константы и младшие слагаемые отбрасывают: $3n^2 + 5n$ — это $O(n^2)$.
- Два вложенных цикла по $n$ — $O(n^2)$; цикл, делящий диапазон пополам, — $O(\log n)$.
- Различают наилучший, средний и наихудший случаи; оценивают и память.
- Пузырёк и вставки — $O(n^2)$; вставки быстры на почти упорядоченном массиве.
- Слияние — $O(n \log n)$ всегда, требует дополнительной памяти, устойчиво.
- Быстрая сортировка — в среднем $O(n \log n)$, в худшем $O(n^2)$ при неудачном опорном элементе.
- Устойчивость — сохранение порядка равных элементов.
Где чаще всего ошибаются
- Считать $O(n \log n)$ медленнее $O(n^2)$ при больших $n$.
- Думать, что быстрая сортировка всегда $O(n \log n)$.
- Учитывать константы при сравнении порядков роста.
Проверить себя
По этой же теме курса есть проверочная работа из 15 заданий на 30 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Программирование (ИТ-класс) · 10–11 классы · Сложность алгоритмов и сортировки