2.3 Оценка эффективности алгоритмов¶
При разработке алгоритма важно заранее понять, достаточно ли он эффективен для заданных ограничений. В соревновательном программировании это особенно критично: если алгоритм слишком медленный, решение не пройдет по времени.
Основная идея оценки проста:
Современный компьютер способен выполнять порядка сотен миллионов операций в секунду.
Этого достаточно, чтобы прикинуть, успеет ли алгоритм уложиться в лимит времени.
1. Грубая оценка количества операций¶
Пусть:
- ограничение по времени — 1 секунда,
- размер входа —
n = 10^5.
Если алгоритм имеет сложность O(n²), то он выполнит примерно:
(10^5)² = 10^10 операций
Это десятки миллиардов операций — значит, программа будет работать десятки секунд. Такой алгоритм явно слишком медленный.
2. Таблица ориентиров¶
При лимите времени около 1 секунды можно ориентироваться на следующие оценки:
| Размер входа | Подходящая сложность |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 5000 | O(n²) |
| n ≤ 10⁶ | O(n log n) или O(n) |
| n очень большое | O(1) или O(log n) |
Это не строгие границы, а практические ориентиры.
3. Как пользоваться этими оценками¶
Допустим, в задаче:
1 ≤ n ≤ 10^5
Из таблицы видно: скорее всего требуется алгоритм со сложностью:
- O(n)
- или O(n log n)
Значит, решения O(n²) даже не стоит рассматривать — они гарантированно не пройдут по времени.
Таким образом, оценка сложности помогает сузить круг идей ещё до написания кода.
4. Влияние констант¶
Важно помнить:
O-нотация скрывает константы.
Например, алгоритм O(n) может выполнять:
- n/2 операций
- или 50n операций
Обе версии имеют сложность O(n), но вторая будет в 100 раз медленнее.
Поэтому:
- асимптотика важна,
- но константы тоже могут играть роль.
Пример: задача о максимальной сумме подотрезка¶
Рассмотрим классическую задачу:
Дан массив из n чисел. Найти максимальную сумму подряд идущих элементов.
Например:
-2 4 -1 3 -5 2
Оптимальный подотрезок:
4 -1 3
Сумма = 6.
Алгоритм 1 — перебор всех подотрезков (O(n³))¶
Идея:
- Перебрать начало отрезка.
- Перебрать конец.
- Для каждого варианта посчитать сумму.
Три вложенных цикла → O(n³).
Подойдет только для n ≤ 500.
Алгоритм 2 — улучшенный перебор (O(n²))¶
Если считать сумму на лету, можно убрать один цикл:
- фиксируем левую границу,
- постепенно двигаем правую,
- накапливаем сумму.
Теперь два вложенных цикла → O(n²).
Подойдет для n ≤ 5000.
Алгоритм 3 — линейный алгоритм (O(n))¶
Можно решить задачу за один проход.
Идея:
- Пусть
current— максимальная сумма подотрезка, заканчивающегося в позиции i. - Тогда:
current = max(a[i], current + a[i])
- Общий максимум обновляется на каждом шаге.
Один цикл → O(n).
Это оптимальная сложность, потому что каждый элемент нужно хотя бы один раз прочитать.
Сравнение на практике¶
| n | O(n³) | O(n²) | O(n) |
|---|---|---|---|
| 10³ | работает | работает | мгновенно |
| 10⁴ | слишком медленно | работает | мгновенно |
| 10⁵ | Чай заварится | слишком медленно | мгновенно |
| 10⁶ | Можно поспать | Чай заварится | работает |
Разница становится колоссальной при больших n.
Итоги¶
- Всегда оценивайте сложность до написания кода.
- Сравнивайте её с ограничениями.
- Используйте таблицу ориентиров.
- Помните, что O-нотация скрывает константы.
- Стремитесь к линейной или близкой к линейной сложности.
Оценка эффективности — это навык, который развивается с практикой. Чем больше задач вы решаете, тем быстрее начинаете чувствовать, какая сложность подходит под заданные ограничения.