Временная сложность

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

Эффективность алгоритмов играет центральную роль в олимпиадном программировании. Когда вы закончили проектировать алгоритм, необходимо ответить на два важных вопроса: «Правильно ли он работает?» и «Сколько времени занимает выполнение?». Разумеется, вас не устроит алгоритм, который выдаёт правильный результат лишь в половине случаев или требует \(1000\) лет для поиска ответа.

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

Для описания временной сложности применяется нотация \(O(\ldots)\), где многоточием представлена некоторая функция. Обычно буквой \(n\) обозначается размер входных данных. Например, если на вход подается массив чисел, то \(n\) — это размер массива, а если строка, то \(n\) — длина строки.

Правила вычисления

Если код включает только линейную последовательность команд, как, например, показанный ниже, то его временная сложность равна \(O(1)\).

a += 1
b += 1
c = a + b

Временная сложность цикла оценивает число выполненных итераций. Например, временная сложность следующего кода равна \(O(n)\), поскольку код внутри цикла выполняется \(n\) раз. При этом предполагается, что многоточием «…» обозначен код с временной сложностью \(O(1)\):

for i in range(n):
    …

Временная сложность следующего кода равна \(O(n^2)\):

for i in range(n):
    for j in range(n):
        …

Вообще, если имеется \(k\) вложенных циклов и в каждом цикле перебирается \(n\) значений, то временная сложность равна \(O(n^k)\).

Временная сложность не сообщает, сколько точно раз выполняется код внутри цикла, она показывает лишь порядок величины, игнорируя постоянные множители. В примерах ниже код внутри цикла выполняется \(3n, \; n + 5\) и \(\lceil \frac{n}{2}\rceil\) раз, но временная сложность в каждом случае равна \(O(n)\):

for i in range(3*n):
    …

for i in range(n + 5):
    …

for i in range(0, n, 2):
    …

Если алгоритм состоит из нескольких последовательных частей, то общая временная сложность равна максимуму из временных сложностей отдельных частей, т. е. самая медленная часть является узким местом. Так, следующий код состоит из трех частей с временной сложностью \(O(n)\), \(O(n^2)\) и \(O(n)\). Поэтому общая временная сложность равна \(O(n^2)\):

for i in range(n):
    …

for i in range(n):
    for j in range(n):
        …

for i in range(n):
    …

Иногда временная сложность зависит от нескольких факторов, поэтому формула включает несколько переменных. Например, временная сложность следующего кода равна \(O(nm)\):

for i in range(n):
    for j in range(m):
        …

Часто встречающиеся оценки временной сложности

Ниже перечислены часто встречающиеся оценки временной сложности алгоритмов:

Сложность алгоритма	Пояснение
\(O(1)\)	Время работы алгоритма с постоянным временем не зависит от размера входных данных. Типичным примером может служить явная формула, по которой вычисляется ответ.
\(O(\log n)\)	В логарифмическом алгоритме размер входных данных на каж дом шаге обычно уменьшается вдвое. Время работы зависит от размера входных данных логарифмически, поскольку \(\log_2n\) — это сколько раз нужно разделить \(n\) на \(2\), чтобы получить \(1\). Отметим, что основание логарифма во временной сложности не указывается.
\(O(\sqrt n)\)	Алгоритм с временной сложностью \(O(\sqrt n)\) медленнее, чем \(O(\log n)\), но быстрее, чем \(O(n)\). Специальное свойство квадратного корня заключается в том, что \(\sqrt n = \frac{n}{\sqrt{n}}\), т. е. \(n\) элементов можно разбить на \(O(\sqrt n)\) порций по \(O(\sqrt n)\) элементов.
\(O(n)\)	Линейный алгоритм перебирает входные данные постоянное число раз. Зачастую это наилучшая возможная временная сложность, потому что обычно, чтобы получить ответ, необходимо обратиться к каждому элементу хотя бы один раз.
\(O(n\log n)\)	Такая временная сложность часто означает, что алгоритм сортирует входные данные, поскольку временная сложность эффективных алгоритмов сортировки равна \(O(n\log n)\). Есть и другая возможность — в алгоритме используется структура данных, для которой каждая операция занимает время \(O(\log n)\).
\(O(n^2)\)	Квадратичный алгоритм нередко содержит два вложенных цикла. Перебрать все пары входных элементов можно за время \(O(n^2)\).
\(O(n^3)\)	Кубический алгоритм часто содержит три вложенных цикла. Все тройки входных элементов можно перебрать за время \(O(n^3)\).
\(O(2^n)\)	Такая временная сложность нередко указывает на то, что алгоритм перебирает все подмножества множества входных данных. Например, подмножествами множества \(\{ 1, 2, 3 \}\) являются \(\varnothing\), \( \{ 1 \}\), \(\{2\}\), \(\{3\}\), \(\{1, 2\}\), \(\{1, 3\}\), \(\{2, 3\} \) и \(\{1, 2, 3\}\).
\(O(n!)\)	Такая временная сложность часто означает, что алгоритм перебирает все перестановки входных элементов. Например, перестановками множества \(\{ 1, 2, 3 \}\) являются \((1, 2, 3)\), \((1, 3, 2)\), \((2,1,3)\), \((2,3,1)\), \((3,1,2)\), \((3,2,1)\).

Алгоритм называется полиномиальным, если его временная сложность не выше \(O(n^k)\), где \(k\) — константа. Все приведенные выше оценки временной сложности, кроме \(O(2^n)\) и \(O(n!)\), полиномиальные. На практике константа \(k\) обычно мала, поэтому полиномиальная временная сложность, грубо говоря, означает, что алгоритм может обрабатывать большие входные данные.

Оценка эффективности

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

Например, предположим, что для задачи установлено временное ограничение — не более одной секунды — и что размер входных данных равен \(n = 10^5\). Если временная сложность алгоритма равна \(O(n^2)\), то он должен будет выполнить порядка \((10^5)^2 = 10^{10}\) операций. Это займет, по меньшей мере, несколько десятков секунд, поэтому такой алгоритм слишком медленный для решения задачи. Но если временная сложность равна \(O(n\log n)\), то количество операций будет равно всего \(10^5 \log 10^5 \approx 1.6 \cdot 10^6\), так что алгоритм гарантированно укладывается в отведенные рамки.

С другой стороны, зная размер входных данных, мы можем попытаться угадать временную сложность алгоритма, требуемую для решения задачи. В таблице ниже приведены некоторые полезные оценки в предположении, что временное ограничение равно \(1\) секунде.

Размер входных данных	Ожидаемая временная сложность
\(n \leq 10\)	\(O(n!)\)
\(n \leq 20\)	\(O(2^n)\)
\(n \leq 500\)	\(O(n^3)\)
\(n \leq 5000\)	\(O(n^2)\)
\(n \leq 10^6\)	\(O(n\log n)\) или \(O(n)\)
\(n\) велико	\(O(1)\) или \(O(\log n)\)

Например, если размер входных данных \(n = 10^5\), то, вероятно, можно ожидать, что временная сложность алгоритма равна \(O(n)\) или \(O(n\log n)\). Обладание этой информацией упрощает проектирование алгоритма, поскольку сразу исключает подходы, приводящие к алгоритму с худшей временной сложностью.

При всем при том важно помнить, что временная сложность — всего лишь оценка эффективности, поскольку она скрывает постоянные множители. Например, алгоритм с временной сложностью может выполнять как \(\frac n2\), так и \(5n\) операций, а это существенно влияет на фактическое время работы.

Авторизация