§ 36. Сложность вычислений

Определения и обозначения

Размер входных данных n — параметр, которым измеряют объём задачи и относительно которого считают затраты алгоритма. Для массива n может быть числом элементов, для текста — числом символов, для графа — числом вершин или рёбер. Выбор зависит от того, какая часть входа влияет на работу алгоритма. Благодаря этому можно сравнивать затраты для маленьких и больших задач.

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

Асимптотическая оценка O(f(n)) описывает скорость роста сложности при больших n. При этом не учитывают постоянные множители и слагаемые, которые растут медленнее главного. Например, выражение 3n² + 5n + 8 имеет порядок O(n²). Оценка показывает общий характер роста, но не точное количество команд.

Полиномиальный алгоритм имеет сложность, ограниченную степенью n, например O(n²), а экспоненциальный — сложность вида O(aⁿ), где a больше 1. При n = 100 величины n² и 2ⁿ различаются несравнимо сильнее, чем при маленьком n. Поэтому полиномиальные методы часто удаётся применять к крупным данным, а экспоненциальные быстро становятся непрактичными. Например, полный перебор подмножеств имеет 2ⁿ вариантов.

Как это устроено

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

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

В последовательных частях программы сначала считают затраты каждой части, а затем складывают их: например, n + n² операций дают выражение n² + n. Вложенные циклы обычно ведут к произведению повторений: если внешний и внутренний циклы выполняются по n раз, получается около n · n операций. Но одинаковая вложенность сама по себе не гарантирует O(n²): важно проверить реальные границы и число повторений. Если внутренний цикл в целом делает лишь постоянное число шагов, итог может быть другим.

Асимптотическая оценка сохраняет слагаемое, которое быстрее остальных растёт при больших n. В сумме n² + n главным становится n², поэтому записывают O(n²): отношение линейной части к квадратичной уменьшается с ростом входа. Так легче сравнивать алгоритмы по масштабу затрат, не отвлекаясь на детали небольшого веса. Однако для маленьких n постоянные множители и отброшенные слагаемые иногда заметно влияют на скорость.

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

Типичные оценки сложности алгоритмов

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

Разбор задач

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

1. После первого элемента алгоритм обрабатывает n − 1 оставшихся значений.
2. С каждым из них выполняется одно сравнение с текущим максимумом, значит, сравнений n − 1.
3. Число сравнений растёт пропорционально n; постоянное вычитание единицы не меняет порядок роста.

Ответ: n − 1 сравнений и сложность O(n). При оценке порядка роста не требуется считать точное число операций всего алгоритма.

Задача 2. Алгоритм сравнивает каждый элемент массива с каждым. Для n = 100 оценим количество сравнений и запишем сложность. Если сравниваются все упорядоченные пары, включая элемент с самим собой, цикл для каждого из 100 элементов делает ещё 100 сравнений. Если алгоритм пропускает сравнение элемента с самим собой или повторную пару, число будет отличаться, но порядок останется квадратичным.

1. В первом цикле выбирается один из 100 элементов.
2. Для каждого выбранного элемента второй цикл проходит по всем 100 элементам, поэтому получается 100 · 100 = 10 000 сравнений.
3. В общем случае произведение n повторений на n повторений даёт n² операций.

Ответ: при указанной схеме — 10 000 сравнений для n = 100 и O(n²). Если сравнивать только разные неупорядоченные пары, точное число будет меньше, но сложность останется O(n²).

Задача 3. Нужно перебрать все подмножества множества из n элементов и сравнить работу при n = 10 и n = 20. Каждый элемент можно либо включить в подмножество, либо не включать, то есть для него есть два независимых выбора. Поэтому общее количество комбинаций определяется произведением двух вариантов для каждого элемента.

1. Для n элементов вариантов будет 2 · 2 · … · 2 = 2ⁿ.
2. При n = 10 получаем 2¹⁰ = 1024 подмножества.
3. При n = 20 получаем 2²⁰ = 1 048 576 подмножеств, то есть в 2¹⁰ = 1024 раза больше, чем при n = 10.

Ответ: сложность перебора O(2ⁿ); увеличение размера с 10 до 20 умножает число проверяемых вариантов в 1024 раза. Поэтому такой полный перебор быстро становится непрактичным.

Типичные ошибки

Считать, что O(n) означает ровно n операций, — ошибка: это порядок роста, а не точный подсчёт. Её допускают, потому что запись похожа на формулу для числа действий. Проверяйте, сколько операций действительно выполняется и какие постоянные множители или дополнительные команды есть; например, 3n сравнений всё равно имеют оценку O(n).

При сложении оценок иногда оставляют все слагаемые или считают их одинаково важными. Но для больших n более быстро растущий член определяет общий порядок: в n² + n оставляют O(n²). Чтобы проверить себя, сравните скорости роста слагаемых при увеличении n и отбросьте те, которые становятся менее значимыми.

Два вложенных цикла не всегда дают O(n²), хотя при n повторениях каждого это обычный результат. Ошибку допускают, ориентируясь только на рисунок кода, а не на границы циклов. Для проверки отдельно посчитайте повторы внешнего и внутреннего циклов и выясните, сколько раз внутреннее тело выполняется в сумме.

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

Связь с другими темами

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

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

Что запомнить

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