Время работы алгоритма

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

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

Кажется, что самый простой способ сравнить два алгоритма – запустить их и посмотреть на время. Например:

Можно решить, что алгоритм A лучше. Но такое сравнение не очень надёжно. Результат зависит от множества вещей:

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

Посмотрим на простой поиск. Нужно найти число 9:

Алгоритм проверяет элементы один за другим:

Количество работы здесь зависит от того, сколько элементов находится в массиве. Для размера входных данных обычно используют обозначение n. Если в массиве пять элементов, то n = 5. Если миллион – n = 1 000 000.

То есть n – это не какое-то специальное значение алгоритма. Это просто удобное обозначение размера входных данных.

Рассмотрим поиск числа, которого в массиве нет:

Чтобы убедиться, что 10 отсутствует, алгоритму придётся проверить каждый элемент:

Если в массиве будет 100 элементов, в таком случае потребуется до 100 проверок. Если n = 1 000 000, проверок может быть 1 000 000.

Количество работы растёт вместе с размером входных данных.

Теперь поместим искомое число 9 в начало:

Алгоритм проверит первый элемент – 9 == 9 – и сразу закончит работу. Получается всего одна проверка. Но если 9 находится в конце:

придётся пройти через весь массив. То есть один и тот же алгоритм может работать по-разному даже при одинаковом размере входных данных. Для массива из пяти элементов:

Если элементов n:

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

Посмотрим ещё раз на алгоритм:

Внутри происходят разные действия:

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

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

Есть отсортированный массив, в котором нужно найти 37:

Первый способ – проверять элементы по очереди. В худшем случае придётся пройти через весь массив: если элементов n = 1 000, проверок может быть около 1 000.

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

При увеличении количества данных алгоритмы могут масштабироваться совершенно по-разному.

Допустим, количество данных увеличилось в десять раз: было n = 100, стало n = 1 000.

Для одного алгоритма количество работы тоже может увеличиться примерно в десять раз. У другого – всего на несколько дополнительных шагов. А у третьего – вырасти в сто раз.

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

Допустим, два алгоритма работают с десятью элементами. Первому требуется 10 условных операций, второму – 100. Разница небольшая, и оба выполнятся почти мгновенно.

Но если элементов станет 100 000, одному алгоритму может понадобиться около 100 000 операций, а другому – 10 000 000 000.

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

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

Теперь рассмотрим другой алгоритм – с n * n операций. Если n увеличится в два раза, работы станет уже примерно в четыре раза больше.

Количество операций – не единственная характеристика алгоритма. Иногда более быстрый способ требует хранить дополнительные данные.

Например, один алгоритм может постоянно использовать только несколько переменных – left, right, mid. А другому может понадобиться создать дополнительный массив почти такого же размера, как исходный. Поэтому при анализе алгоритмов обычно рассматривают две вещи:

Пока мы сосредоточимся на времени.

Теперь у нас есть основная идея. Мы не спрашиваем «сколько миллисекунд занял алгоритм на моём компьютере?». Вместо этого спрашиваем: как меняется количество его работы, когда увеличивается размер входных данных?

Например, при n = 10, n = 100, n = 1 000 и n = 1 000 000. Некоторые алгоритмы почти не почувствуют такой рост. Другие станут заметно медленнее. А некоторые очень быстро станут практически непригодными.

Чтобы коротко описывать такое поведение, используют специальную запись – Big O.