Оптимизация алгоритма
Оптимизация алгоритма — это изменение его шагов или структуры так, чтобы он выполнял ту же задачу с меньшими затратами времени, памяти или числа действий, сохраняя правильный результат.
Что именно оптимизируют
Перед изменением алгоритма оценивают его сложность: как растёт число действий и объём памяти при увеличении размера входных данных. Оптимизация может заключаться в удалении повторных вычислений, досрочном завершении цикла, использовании подходящей структуры данных или замене одного метода другим.
- Время: алгоритм выполняется за меньшее число шагов.
- Память: требуется меньше дополнительных переменных и массивов.
- Количество действий: убираются ненужные проверки и повторная обработка данных.
Сравнение вариантов
Если два алгоритма дают одинаковый результат, предпочтительнее тот, у которого меньше оценка затрат для нужных размеров входа. Например, последовательный поиск проверяет элементы по очереди, а двоичный поиск в отсортированном массиве каждый раз отбрасывает половину вариантов. Поэтому при большом массиве двоичный поиск обычно существенно быстрее.
Здесь \(T(n)\) — число действий или время работы алгоритма для входа размера \(n\). Неравенство показывает цель оптимизации, но сравнивать нужно также требования к памяти и ограничения задачи.
Пусть нужно найти сумму чисел от \(1\) до \(n\). Цикл сложит все числа за \(n\) действий. Если использовать формулу \(S=\frac{n(n+1)}{2}\), сумма находится за постоянное число действий: не требуется перебирать все элементы. Результат тот же, но алгоритм быстрее при больших \(n\).
Отладка алгоритма ищет и исправляет ошибки, а оптимизация улучшает затраты уже корректного алгоритма. Нельзя считать изменение оптимизацией, если после него алгоритм перестал выдавать правильный результат.
Какое изменение является оптимизацией корректного алгоритма?
Главное
- Оптимизация сохраняет правильность алгоритма и уменьшает затраты ресурсов.
- Оценивают время, память и число действий; для сравнения используют сложность алгоритма.
- Удаление повторных вычислений, досрочное завершение и выбор более эффективного метода — типичные приёмы оптимизации.