Как определить сложность алгоритма: пошаговое решение

Дано: фрагмент кода из двух частей: цикл по $i$ от 1 до $n$ с вложенным циклом по $j$ от $i$ до $n$, а после них цикл, который делит $k$ пополам, пока $k > 1$. Размер входа $n = 16$. Найти: точное число операций $T(16)$ и оценку сложности в O-нотации.

Считаем, сколько раз выполняется тело каждого цикла, складываем последовательные части и оставляем самый быстрорастущий член. Ответ: $T(n) = \dfrac{n(n+1)}{2} + \lfloor \log_2 n \rfloor$, при $n = 16$ это $136 + 4 = 140$ операций, сложность $O(n^2)$. Калькулятор сверху пересчитает всё под другое $n$ и другие виды циклов, ниже решение по шагам.

Решение по шагам

Дано. Фрагмент на Python. За одну операцию принимаем одно выполнение тела цикла:

s = 0
for i in range(1, n + 1):        # внешний цикл: i = 1..n
    for j in range(i, n + 1):    # внутренний цикл: j = i..n
        s += 1                   # операция A
k = n
t = 0
while k > 1:                     # цикл деления пополам
    k //= 2
    t += 1                       # операция B

Шаг 1. Внутренний цикл при фиксированном $i$. Переменная $j$ пробегает значения от $i$ до $n$ включительно, то есть $n - i + 1$ значений. При $i = 1$ тело выполнится 16 раз, при $i = 2$ пятнадцать раз и так далее, пока при $i = 16$ не останется одна итерация:

Шаг 2. Суммируем по внешнему циклу. Число итераций внутреннего цикла зависит от $i$, поэтому перемножать границы нельзя: итерации надо сложить по всем $i$.

$$A(n) = \sum_{i=1}^{n} (n - i + 1) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}.$$

При $n = 16$ получаем $A(16) = \dfrac{16 \cdot 17}{2} = 136$.

Шаг 3. Цикл с делением пополам. Переменная $k$ стартует с 16 и после каждой итерации уменьшается вдвое:

После четвёртой итерации $k = 1$, условие $k > 1$ ложно, и цикл останавливается. В общем виде число итераций равно $B(n) = \lfloor \log_2 n \rfloor$, при $n = 16$ это $\log_2 16 = 4$.

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

$$T(n) = \frac{n(n+1)}{2} + \lfloor \log_2 n \rfloor, \qquad T(16) = 136 + 4 = 140.$$

Шаг 5. Оставляем главный член. Раскроем скобки: $T(n) = \tfrac{1}{2}n^2 + \tfrac{1}{2}n + \lfloor \log_2 n \rfloor$. С ростом $n$ квадратичное слагаемое обгоняет линейное и логарифмическое, а множитель $\tfrac{1}{2}$ в O-нотации отбрасывается.

Ответ. Тело цикла выполняется $T(16) = 140$ раз: 136 раз во вложенных циклах и 4 раза в цикле деления пополам. Временная сложность фрагмента $O(n^2)$, точнее $\Theta(n^2)$.

Формула и откуда она берётся

Запись $f(n) = O(g(n))$ означает, что начиная с некоторого $n_0$ функция $f$ не превосходит $g$, умноженную на константу:

$$f(n) \le c \cdot g(n) \quad \text{для всех } n \ge n_0.$$

Для нашего фрагмента подходят $c = 1$ и $n_0 = 1$: например, $T(16) = 140 \le 16^2 = 256$. Снизу $T(n)$ ограничена функцией $\tfrac{1}{2} n^2$, поэтому оценка точная и записывается как $\Theta(n^2)$. Константы и младшие члены на класс не влияют: они меняют время в разы, но не меняют порядок роста.

Из определения вытекают три правила, по которым сложность определяют прямо по коду. Последовательные блоки складываются, и в сумме остаётся самый тяжёлый: $O(n^2) + O(\log n) = O(n^2)$. Вложенные циклы с независимыми границами перемножаются: два цикла по $n$ дают $n \cdot n$. Если граница внутреннего цикла зависит от внешнего счётчика, как здесь $j$ от $i$, итерации суммируют по всем $i$.

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

Почему цикл с делением пополам даёт логарифм

После $t$ итераций переменная равна $n / 2^t$ с округлением вниз. Цикл заканчивается, когда она дошла до единицы, то есть когда $2^t \ge n$. Отсюда $t \approx \log_2 n$. Так же ведёт себя любой цикл, который умножает или делит счётчик на константу: шаг $j = 2j$, $j = 3j$ или $k = k / 10$. Основание логарифма в O-нотации не пишут, потому что $\log_a n$ и $\log_b n$ отличаются лишь постоянным множителем.

Важно, где стоит такой цикл. У нас он идёт после вложенных и добавляет всего 4 операции. Если поставить цикл с удвоением на место внутреннего цикла по $j$, он выполнится $n$ раз по $\lfloor \log_2 n \rfloor + 1$ итераций, и весь фрагмент станет $O(n \log n)$. Этот вариант есть в калькуляторе: при $n = 16$ вложенная часть даёт $16 \cdot 5 = 80$ операций, итог 84.

Тот же порядок $n \log n$ получается у сортировки слиянием: $\log_2 n$ уровней деления и по $n$ операций слияния на каждом. Приём деления пополам лежит и в основе двоичного поиска, подробнее он разобран в статье про бинарный поиск по ответу.

Если же счётчик уменьшается вычитанием ($k = k - 1$), цикл сделает $n - 1$ итерацию, и это уже линейная часть. Переключи хвостовой цикл в калькуляторе: при $n = 16$ он даст 15 операций вместо 4, итог станет 151, но оценка $O(n^2)$ не изменится.

Проверка ответа удвоением n

Оценку легко проверить без формул: посчитать операции при $n$ и при $2n$ и посмотреть, во сколько раз выросло число. Для нашего фрагмента $T(32) = 528 + 5 = 533$, и $533 / 140 \approx 3{,}81$. При переходе к $n = 64$ отношение равно $2086 / 533 \approx 3{,}91$ и приближается к 4, как и положено квадратичному алгоритму.

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

Рекурсия: основная теорема кратко

Если алгоритм рекурсивный, вместо суммы по циклам получается рекуррентное соотношение. Для алгоритмов, которые делят задачу на $a$ подзадач размера $n/b$ и тратят $f(n)$ на разбиение и сборку, работает основная теорема:

$$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n).$$

Сравнивают $f(n)$ с $n^{\log_b a}$. Если $f$ растёт медленнее, ответ $\Theta(n^{\log_b a})$. Если они одного порядка, ответ $\Theta(n^{\log_b a} \log n)$. Если $f$ растёт быстрее и выполнено условие регулярности, ответ $\Theta(f(n))$.

Двоичный поиск: $T(n) = T(n/2) + 1$, здесь $a = 1$, $b = 2$, $n^{\log_2 1} = 1$, случай равенства, итог $\Theta(\log n)$. Сортировка слиянием: $T(n) = 2T(n/2) + n$, итог $\Theta(n \log n)$. Умножение Карацубы: $T(n) = 3T(n/2) + n$, итог $\Theta(n^{\log_2 3}) \approx \Theta(n^{1{,}585})$.

Теорема не покрывает соотношения вида $T(n) = T(n-1) + n$, где задача уменьшается на единицу, а не в разы. Их раскрывают подстановкой в сумму и получают тот же треугольник $n(n+1)/2$, что и в нашем фрагменте. Именно так выводится квадратичный худший случай быстрой сортировки.

Частые ошибки

• Перемножают границы, когда внутренний цикл зависит от внешнего. Для $j$ от 1 до $i^2$ произведение $n \cdot n$ даст неверный ответ: сумма $\sum i^2$ растёт как $n^3/3$, и сложность будет $O(n^3)$.
• Считают цикл с делением пополам линейным. Цикл $k = k / 2$ делает $\lfloor \log_2 n \rfloor$ итераций: при $n = 16$ их 4, а не 16.
• Перемножают последовательные блоки. Цикл по $n$, за которым идёт ещё один цикл по $n$, даёт $2n$ операций, то есть $O(n)$, а не $O(n^2)$. Умножение нужно только для вложенности.
• Оставляют в ответе константы и младшие члены. Запись $O(n^2/2 + \log n)$ формально не ошибка, но в ответе ждут $O(n^2)$: класс определяется главным членом.
• Принимают цикл с постоянной границей за зависящий от n. Цикл от 1 до 100 внутри цикла по $n$ даёт $100n$ операций, это $O(n)$, а не $O(n^2)$.
• Путают вычислительную сложность с цикломатической. Цикломатическая сложность считает число независимых путей в графе программы и от $n$ не зависит, время работы она не оценивает.

FAQ

Чем отличаются O, Θ и Ω? $O$ задаёт верхнюю границу роста, $\Omega$ нижнюю, $\Theta$ обе сразу. Для нашего фрагмента верны все три записи: $O(n^2)$, $\Omega(n^2)$ и $\Theta(n^2)$. Когда в задаче просят определить сложность, обычно ждут точную оценку, записанную через $O$.

Какую сложность писать: худшего или среднего случая? По умолчанию указывают худший случай: он гарантирует, что алгоритм не будет работать дольше. В нашем фрагменте нет ветвлений, поэтому все случаи совпадают. У быстрой сортировки они различаются: $O(n \log n)$ в среднем и $O(n^2)$ в худшем.

Как определить сложность алгоритма по памяти? Тем же способом, только считают не операции, а объём дополнительных данных: массивы, глубину рекурсии, вспомогательные структуры. Наш фрагмент хранит лишь $s$, $k$ и $t$, поэтому его затраты памяти $O(1)$.

Можно ли определить сложность, просто замерив время программы? Замер подсказывает класс, если удваивать $n$ и смотреть на отношение времён, но не доказывает его. Время зависит от кэша процессора, интерпретатора и от младших членов, которые на малых $n$ ещё заметны. Строгий ответ даёт подсчёт итераций.

Коротко

1. Для каждого цикла определи, сколько раз выполнится его тело в зависимости от $n$.
2. Если внутренний цикл зависит от внешнего счётчика, просуммируй итерации: $\sum_{i=1}^{n}(n-i+1) = \tfrac{n(n+1)}{2}$.
3. Цикл, который делит или умножает счётчик на константу, даёт $\log_2 n$ итераций, а не $n$.
4. Последовательные части сложи, вложенные перемножь или просуммируй, оставь главный член без констант.
5. В примере $T(16) = 136 + 4 = 140$, сложность $O(n^2)$, а удвоение $n$ увеличивает число операций почти в 4 раза.