Задания № 22, 23 · ЕГЭ

Сложность алгоритма

Как измеряют время и память, нужные алгоритму
2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Сложность алгоритмаТермин связан со сложностью вычислений: чем быстрее растут затраты при увеличении $n$, тем сложнее алгоритм.
Сложность алгоритма — зависимость количества вычислительных ресурсов, необходимых для решения задачи, от размера входных данных. Размер входа обозначают \(n\), а сложность чаще всего описывают порядком роста функции: например, \(O(1)\), \(O(n)\) или \(O(n^2)\).

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

Основные виды сложности

  • Временная сложность — сколько операций или условных единиц времени требуется алгоритму.
  • Пространственная сложность — сколько дополнительной памяти требуется во время работы.
  • Асимптотическая сложность — порядок роста затрат при больших \(n\), без учёта постоянных множителей и менее значимых слагаемых.
\[T(n) = O(f(n))\]

Запись \(T(n)=O(f(n))\) означает, что время работы растёт не быстрее порядка \(f(n)\) с точностью до постоянного множителя. Например, алгоритм с \(3n+5\) операциями имеет сложность \(O(n)\), а алгоритм с \(2n^2+n\) — \(O(n^2)\). Классы таких оценок подробно сравниваются в статье классы сложности алгоритмов.

№
Пример

Алгоритм последовательно просматривает все \(n\) элементов массива и ищет максимальный. Каждый элемент проверяется один раз, поэтому временная сложность равна \(O(n)\). Если алгоритм хранит только текущий максимум, дополнительная память имеет сложность \(O(1)\).

!
Не путайте

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

Проверьте себя

Какова временная сложность двух вложенных циклов, каждый из которых выполняется примерно \(n\) раз?

Главное за минуту

Главное

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