Сколько шагов делает алгоритм

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

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

Раньше нас интересовало только одно: даёт ли алгоритм правильный ответ. Теперь зададим второй вопрос — а быстро ли? Компьютер не бесконечно быстр, и когда данных становится много (миллион чисел, тысячи пользователей), разница между «хорошим» и «плохим» алгоритмом становится пропастью: секунда против часов. Чтобы предсказать это заранее, не запуская программу, считают число шагов.

Зачем это нужно

Представьте, что нужно найти, есть ли повторяющееся число в списке из миллиона элементов. Один способ сравнивает каждое число с каждым, другой — проходит список один раз. Оба верны, но первый сделает примерно $10^{12}$ операций (это часы работы), а второй — около $10^6$ (доли секунды). На ЕГЭ часто спрашивают: «сколько раз выполнится тело цикла?» — и это ровно подсчёт шагов. А в жизни умение прикинуть сложность отделяет работающую программу от зависающей.

Важно понять главное: нас не интересует время в секундах. Оно зависит от компьютера, языка и тысячи мелочей — на быстрой машине медленный алгоритм может обогнать быстрый на старой. Поэтому считают не секунды, а число элементарных операций как функцию от размера данных n. Эта оценка не зависит от железа и предсказывает поведение программы на любом входе: будет ли она работать при $n = 100$, при $n = 10^6$ или «повиснет».

Считаем число операций

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

n = 1000
count = 0
for i in range(n):
    count += 1   # считаем сами итерации
print(count)

Вывод:

1000

Ровно n итераций. Если внутрь вложить второй цикл, который тоже крутится n раз, на каждый шаг внешнего придётся n шагов внутреннего — итого $n \\cdot n = n^2$.

n = 1000
count = 0
for i in range(n):
    for j in range(n):
        count += 1
print(count)

Вывод:

1000000

Один цикл дал 1000 шагов, вложенный — миллион. Это и есть разница между линейным и квадратичным ростом.

Линейный и квадратичный рост

Точное число операций обычно не важно — важно, как оно растёт, когда n увеличивается. Эту скорость роста и записывают «O-большим»:

• Линейная сложность $O(n)$: данных вдвое больше — работы вдвое больше. Один проход по списку.
• Квадратичная сложность $O(n^2)$: данных вдвое больше — работы вчетверо больше. Два вложенных цикла, «каждый с каждым».

Формально для квадратичного алгоритма число шагов

$$ T(n) = n^2 \\Rightarrow T(2n) = (2n)^2 = 4 n^2 = 4 \\cdot T(n) $$

То есть удвоение n учетверяет время. Для линейного — лишь удваивает: $T(2n) = 2n = 2 \\cdot T(n)$. Постоянные множители и младшие слагаемые в записи $O$ отбрасывают: $O(3n + 5)$ — это всё равно $O(n)$, потому что при больших n рост определяет именно старший член.

Как это работает

Чтобы прочувствовать пропасть между $O(n)$ и $O(n^2)$, посмотрите на таблицу. Колонки — число операций при разном размере данных n.

Пока n маленькое (10–100), разница незаметна — обе программы отработают мгновенно. Но при $n = 10^6$ линейный алгоритм делает миллион шагов (доли секунды), а квадратичный — триллион (это часы). Именно поэтому «правильно, но медленно» на больших данных равносильно «не работает».

Как определить сложность по коду? Считайте глубину вложенности циклов, зависящих от n. Нет циклов по n — это $O(1)$ (мгновенно, не зависит от данных). Один цикл — $O(n)$. Цикл в цикле — $O(n^2)$. Три уровня — $O(n^3)$.

Вернёмся к задаче про повтор в списке, с которой начали. Наивное решение сравнивает каждый элемент с каждым — это два вложенных цикла, то есть $O(n^2)$: на миллионе чисел триллион сравнений. Но ту же задачу можно решить одним проходом, складывая встреченные числа в множество и проверяя, не встречалось ли текущее раньше; такая проверка почти мгновенна. Получается $O(n)$ — миллион шагов вместо триллиона. Это и есть смысл изучения сложности: понять, что у задачи бывает не только «работающее», но и «быстрое» решение, и научиться выбирать второе.

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

• Считать два цикла подряд как $O(n^2)$. Если циклы идут друг за другом, а не вложены, шагов $n + n = 2n$ — это $O(n)$, а не $O(n^2)$. Квадрат даёт только вложенность.
• Гнаться за точным числом. Неважно, $3n$ или $5n + 10$ — для оценки роста это $O(n)$. Считают порядок, а не точную формулу.
• Забыть про размер данных. Сложность $O(n^2)$ не «плохая» сама по себе: на $n = 50$ это 2500 шагов — мгновенно. Проблема возникает только на больших n.
• Путать цикл с фиксированным числом повторов и цикл по n. for k in range(100) внутри цикла по n — это всё ещё $O(n)$ (100 — константа), а не $O(n^2)$.

Итоги

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