Временная и пространственная сложность алгоритма

Временная и пространственная сложность показывают, как растут затраты алгоритма при увеличении входных данных. Первая описывает число операций, вторая - объём памяти. Например, для массива из восьми элементов полный проход выполняет восемь сравнений с заданным значением, а перебор всех упорядоченных пар - 64 сравнения. Измените размер массива в калькуляторе и посмотрите, как расходятся результаты. Это учебный подсчёт сравнений: реальные секунды зависят ещё и от машины и реализации.
Что именно измеряют
Размер входа нужно определить до вычислений. Для массива это число элементов, для строки - число символов, а для графа одного параметра может не хватить: обычно отдельно указывают число вершин и рёбер . Время в анализе - функция количества выбранных элементарных действий, а не показание секундомера. В зависимости от задачи считают сравнения, присваивания или суммарное число операций в оговорённой модели.
Пространственная сложность описывает память во время работы алгоритма. Часто отдельно называют дополнительную память: ячейки, выделенные сверх уже полученного входа. Тогда массив из элементов не включают в эту оценку, но его новую копию включают. Нужно также оговорить, учитывается ли выходной массив. В примерах ниже вход и вывод исключены, а каждый элемент и счётчик занимают по одной ячейке фиксированного размера.
Как читать O, Ω и Θ
Запись задаёт асимптотическую верхнюю границу: существуют положительная константа и порог , после которого . Она описывает рост при достаточно больших , не точное количество действий. Например, принадлежит : постоянный множитель и слагаемое не меняют линейный порядок роста.
Символ обозначает нижнюю асимптотическую границу, а - одновременно верхнюю и нижнюю границы одного порядка. Поэтому и также , хотя последняя оценка слишком грубая. Большое O само по себе не означает худший случай: это верхняя граница выбранной функции затрат. В условии следует отдельно сказать, рассматривается лучший, средний или худший вход. Формальные определения и подсчёт операций разобраны в материалах MIT по анализу алгоритмов.
Один проход и все пары: расчёт
Пусть первый алгоритм проверяет каждый элемент массива относительно фиксированного порога, не прерывая проход. Он делает ровно сравнений, то есть по этой операции. Второй алгоритм для каждого элемента сравнивает его со всеми элементами, включая его самого. Число сравнений равно , то есть .
| Элементов | Один проход | Все упорядоченные пары |
|---|---|---|
| 4 | 4 | 16 |
| 8 | 8 | 64 |
| 16 | 16 | 256 |

При удвоении число сравнений первого алгоритма удваивается, а второго увеличивается в четыре раза. Здесь пара отличается от , и самосравнения включены. Если нужны только разные неупорядоченные пары, их будет : точное число изменится, но порядок останется квадратичным. Нельзя автоматически считать каждый вложенный цикл квадратичным: если внутренний цикл ограничен константой, суммарная работа может быть линейной.
Откуда берутся основные порядки
Для анализа выпишите, сколько раз исполняется существенная операция. Если после каждого шага остаётся половина диапазона, потребуется примерно шагов: это . При одном полном проходе получается , при двух полных вложенных проходах - . Если два независимых последовательных прохода обрабатывают один массив, их стоимости складываются: , а не .
Сортировка слиянием делит данные на уровни и на каждом уровне обрабатывает суммарно порядка элементов, что приводит к времени при стандартной реализации. При этом нужно отдельно учитывать используемый буфер. Для сравнения, пирамидальная сортировка показывает другой способ получить оценку и другую организацию памяти.
Размеры разных частей входа не следует смешивать без основания. Если внешний цикл проходит строк, а внутренний - столбцов, работа составляет . Назвать её можно только при дополнительном условии, например когда . Выбор модели операций тоже важен: сравнение фиксированных чисел удобно считать постоянным, но сравнение длинных строк может зависеть от их длины.
Как считать дополнительную память
Алгоритм полного прохода может хранить текущий индекс и счётчик подходящих элементов. Их число не растёт с , поэтому в принятой модели дополнительная память равна . Если сначала создать копию массива, она займёт ячеек, и оценка станет , даже если затем алгоритм делает лишь один проход.
Для рекурсии учитывают стек вызовов: если одновременно остаются активными вызовов и каждый хранит фиксированное число ячеек, понадобится дополнительной памяти. Сам факт рекурсии не определяет глубину: она зависит от алгоритма и входа. У стека и очереди организация хранения тоже влияет на оценку операций и объёма данных.
Возможен обмен времени на память. Например, сохранение уже вычисленных результатов иногда устраняет повторную работу, но требует таблицы. В основах динамического программирования такой приём разбирается на задачах с повторяющимися подзадачами. Для корректного сравнения двух программ обязательно используйте одинаковые правила учёта входа, результата и служебных структур.
Как разобрать алгоритм по шагам
Начните с конкретной постановки. Запишите, что подаётся на вход, какие результаты нужны и что обозначает каждый параметр размера. Затем найдите операции, число которых меняется вместе с размером входа. Для цикла посчитайте число итераций, для вложенных циклов - сколько раз внутреннее тело выполняется на каждой внешней итерации. Если границы зависят от индекса, запишите сумму, а не подставляйте квадрат автоматически.
Например, цикл по индексам от нуля до конца массива, внутри которого второй индекс идёт только после первого, перебирает разные неупорядоченные пары. Для первого индекса выполняется на одно сравнение меньше числа элементов, для следующего ещё на одно меньше. Сумма этих слагаемых даёт приведённую выше формулу для пар. Учтите также подготовку данных и создание результата: они могут определять итоговые затраты, если сама основная операция дешева.
После этого перечислите одновременно существующие структуры в памяти. Два буфера размером по всему входу занимают линейный объём, хотя их два; буфер, существующий лишь в течение одного шага, не следует суммировать по числу шагов как будто все его копии живут одновременно. Для оценки пикового расхода важно максимальное количество ячеек, занятых в один момент. Если реализация хранит все результаты попарных сравнений, таблица потребует квадратичной памяти. Если только увеличивает один счётчик и отбрасывает каждый результат, дополнительная память остаётся постоянной.
Наконец, проверьте крайние случаи: пустой вход, один элемент и данные, вызывающие раннюю остановку. Они полезны для проверки точной формулы и корректности программы, хотя конечное число малых значений само по себе не меняет асимптотический порядок. Указывайте допущения рядом с ответом: без них два внешне разных результата могут оба быть верны.
Лучший, средний и худший случаи
Рассмотрим поиск значения в неотсортированном массиве с остановкой при первом совпадении. Лучший случай - совпадение на первом месте: одно сравнение. Худший - элемент отсутствует или стоит последним: сравнений. Средний случай требует указать распределение входов: без предположений о вероятностях единственного среднего числа нет.
Та же задача меняет оценку при другой структуре данных. В поиске в двоичном дереве число шагов зависит от высоты дерева: сбалансированная и вытянутая формы ведут себя по-разному. Называя сложность, уточняйте и свойства входа, и рассматриваемый случай, иначе формула легко вводит в заблуждение.
Асимптотика полезна для прогноза при росте данных, но не заменяет измерения на целевой системе. Константы, выделение памяти, кэш и особенности входа способны изменить практический результат на небольших размерах. Сначала используйте анализ, чтобы понять масштабирование, затем сравнивайте корректные реализации на представительных данных.
Частые ошибки
- Считать точным числом операций. Это класс верхних границ; точная формула зависит от того, что именно считается.
- Перемножать последовательные циклы. Их стоимости складываются; перемножение возникает, когда проходы вложены друг в друга.
- Забывать стек вызовов и копии. Они занимают дополнительную память, даже если в коде мало явно объявленных переменных.
- Называть худшим случаем без уточнения. Сначала выберите функцию затрат для нужного случая, затем задайте её границу.
- Сравнивать разные постановки памяти. Одна оценка может включать вход или выход, а другая - только временный буфер.
FAQ
Может ли алгоритм иметь время и память ?
Да. Полный проход с одним счётчиком имеет такие оценки, если входной массив не включён в дополнительную память, а счётчик считается ячейкой фиксированного размера.
Всегда ли быстрее ?
Нет. Обозначения описывают рост, а не конкретные секунды. Для небольшого входа константы и реализация могут сделать линейное решение быстрее.
Нужно ли считать выходные данные в пространственной сложности?
Зависит от соглашения. Укажите его явно: дополнительная память часто исключает вход, а вопрос включения результата нужно оговорить отдельно.
Коротко
Временная сложность характеризует рост числа операций, пространственная - рост используемой памяти. Определите размер входа, модель операций и правило учёта памяти; затем посчитайте действия и укажите случай. Один полный проход даёт сравнений, все упорядоченные пары - , а копия входа требует дополнительных ячеек.
Читайте также

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

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

Сортировка слиянием: как работает merge sort
Сортировка слиянием на примере массива: разбор проходов и числа сравнений, устойчивость, оценка времени и памяти, реализация на Python и области применения.

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

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

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