Перейти к содержимому
Topos Uranos
Русский

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

Краткое содержание

До сих пор курс судил об алгоритмах по одному-единственному вопросу: делают ли они то, что обещают? Этот урок добавляет второй, от которого зависит, пригодна ли правильная программа на практике: во что она обходится? Сложность сначала измеряется без часов, подсчётом того, сколько раз выполняется доминирующая операция, и оказывается функцией размера nn данных. В этой функции важно не её значение при данном nn, а то, как она растёт: таблица значений nn, nlog⁡nn \log n, n2n^2 и 2n2^n показывает, что различия между алгоритмами, незаметные при десяти данных, превращаются в пропасть при миллионе. Нотация OO вводится как сокращённая запись этих порядков роста, без формального определения, на примерах, уже встречавшихся в курсе: алгоритм Евклида логарифмический; сумма вектора линейная; сравнение всех пар квадратичное; наивное вычисление чисел Фибоначчи экспоненциальное. Затем время измеряется часами из <chrono>, std::chrono::steady_clock, и объясняется, почему одно измерение обманывает, почему измеряют с оптимизацией и без санитайзеров и как сопоставить измерение с предсказанием: при удвоении nn линейный алгоритм удваивает своё время, а квадратичный увеличивает его вчетверо.

Цели обучения

  1. Подсчитывать доминирующие операции алгоритма с одним или двумя циклами как функцию размера nn данных.
  2. Относить алгоритм к константным, логарифмическим, линейным, nlog⁡nn \log n или квадратичным и предсказывать, как меняется его время при удвоении nn.
  3. Измерять время выполнения с помощью std::chrono::steady_clock и сравнивать измерение с предсказанием.
  4. Выбирать между двумя алгоритмами для заданного размера данных, обосновывая выбор порядком роста.

Подсчёт операций

Второй вопрос

Уроки Проектирование правильных циклов и Рекурсия научили доказывать, что алгоритм правилен: что он завершается и что его результат удовлетворяет постусловию. Однако урок Численные алгоритмы показал два одинаково правильных теста на простоту, один примерно с nn делениями, другой примерно с n\sqrt{n}, а урок Рекурсия показал два правильных способа вычислить F30F_{30}, один с 2 692 5372\,692\,537 вызовами, другой с 29 сложениями. Если это так, правильности недостаточно для выбора: из двух правильных алгоритмов один может ответить мгновенно, а другой не завершиться прежде, чем ответ потеряет значение. Поэтому второй вопрос, который задают алгоритму, таков: во что он обходится.

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

Размер и доминирующая операция

Подсчитывать все шаги (каждое сложение, каждое сравнение, каждое увеличение индекса, каждое обращение к памяти) было бы утомительно и бесполезно, потому что почти все они сопровождают один главный шаг в постоянной пропорции. Поэтому выбирают доминирующую операцию: ту, что выполняется не реже любой другой, с точностью до постоянного множителя, и потому представляет их все. В сумме элементов вектора это сложение; в поиске максимума это сравнение; в тесте на простоту это деление. Число её выполнений выражается как функция размера входа, который обозначают nn: это число элементов вектора, проверяемое число, число цифр.

Простой цикл, который обходит вектор из nn элементов и выполняет с каждым фиксированный объём работы, выполняет свою доминирующую операцию nn раз. Поиск максимума непустого вектора, напротив, начинает с первого элемента как кандидата и сравнивает с ним каждый из остальных: n−1n - 1 сравнений. Разница между nn и n−1n - 1 реальна, но, как будет видно в третьем параграфе, она не меняет ничего из того, что важно.

Худший случай

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

Вложенные циклы

Урок Циклы научил считать итерации двух вложенных циклов. Если внутренний всегда делает mm итераций на каждую из nn итераций внешнего, внутреннее тело выполняется n⋅mn \cdot m раз. Если внутренний зависит от внешнего, суммируют построчно. При работе с коллекциями чаще всего встречается случай всех пар: каждый элемент сравнивают с каждым из следующих за ним, как при проверке, есть ли в векторе повторы.

Программа на C++
#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} сравнений; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}
Вывод
n =     10:         45 сравнений; n(n - 1)/2 = 45n =    100:       4950 сравнений; n(n - 1)/2 = 4950n =   1000:     499500 сравнений; n(n - 1)/2 = 499500n =  10000:   49995000 сравнений; n(n - 1)/2 = 49995000

Счётчик занимает место сравнения, которое сделал бы настоящий алгоритм. На итерации ii внешнего цикла внутренний идёт от i+1i + 1 до n−1n - 1 и делает n−1−in - 1 - i итераций; так что всего получается (n−1)+(n−2)+⋯+1+0(n - 1) + (n - 2) + \cdots + 1 + 0, сумма из урока Циклы:

∑i=0n−1(n−1−i)=n(n−1)2\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2}

Вывод подтверждает формулу для каждого размера. Счётчик имеет тип long long, потому что начиная с nn около шестидесяти пяти тысяч число пар превышает максимум int (32-битного на этой платформе), и формула по той же причине умножает после преобразования: счётчик квадратичного алгоритма переполняется гораздо раньше, чем данные.

Заметим уже сейчас то, что обобщит третий параграф: при умножении nn на 10 число сравнений умножается примерно на 100. При десяти данных 45 сравнений; при десяти тысячах почти пятьдесят миллионов.