Оценка времени работы алгоритма

Что такое время работы алгоритма

Время работы алгоритма — это оценка того, сколько элементарных действий выполнит программа, чтобы решить задачу. Чем больше входные данные, тем больше шагов делает алгоритм. Нас интересует не точное число секунд на конкретном компьютере, а то, как растёт число действий при увеличении объёма данных.

Допустим, в массиве n элементов. Если алгоритм просматривает каждый элемент один раз, он делает примерно n действий. Если для каждого элемента он перебирает все остальные, действий будет около n*n. Эта зависимость и определяет, насколько алгоритм быстр.

Сравнение скорости роста

Рассмотрим, как меняется число действий для разных алгоритмов при росте n.

Видно, что квадратичный алгоритм при больших данных становится во много раз медленнее. Поэтому при выборе способа решения важно оценивать порядок числа действий, а не только проверять работу на маленьких примерах.

Основные типы зависимостей

• Постоянное время — число действий не зависит от n, например взять элемент массива по индексу.
• Линейное — действий примерно столько же, сколько элементов: один проход по массиву.
• Квадратичное — вложенный перебор всех пар элементов набора.

Пример подсчёта действий

Подсчитаем, сколько раз выполнится тело внутреннего цикла:

Внешний цикл повторяется n раз, и при каждом повторе внутренний делает ещё n шагов. Всего получается n*n действий — это квадратичный алгоритм.

Частая ошибка: считать, что два отдельных цикла подряд дают квадрат. Если циклы идут друг за другом, а не вложены, действий будет n + n, то есть линейно. Квадрат появляется только при вложенности циклов.

Зачем это нужно

Понимание скорости роста помогает заранее предсказать, справится ли программа с большими данными. Например, перебор всех пар для миллиона элементов потребует триллион действий — это слишком долго. А линейный проход выполнится почти мгновенно. Поэтому опытный программист сначала прикидывает порядок числа действий, а уже потом пишет код.

Лучший, средний и худший случаи

Иногда число действий зависит не только от размера данных, но и от их расположения. Например, при поиске нужного элемента в массиве в лучшем случае он окажется первым, и хватит одного действия. В худшем случае его не будет вовсе, и придётся просмотреть все n элементов. Поэтому скорость алгоритма обычно оценивают по худшему случаю — он гарантирует, что программа не окажется медленнее ожидаемого.

Такая оценка по худшему случаю удобна тем, что не зависит от удачного или неудачного набора данных. Она показывает верхнюю границу числа действий и помогает честно сравнивать разные алгоритмы между собой.

Кратко о главном

• Время работы оценивают по числу действий в зависимости от размера данных n.
• Линейный алгоритм делает порядка n действий, квадратичный — порядка n*n.
• Вложенные циклы дают квадрат, последовательные — сумму.
• Скорость обычно оценивают по худшему случаю, чтобы получить надёжную верхнюю границу.
• Чем медленнее растёт число действий, тем лучше алгоритм работает на больших данных.