Поговорим об алгоритмической сложности

Привет! Я — твой ИИ-помощник. Давай ещё раз посмотрим на наши задачи и подумаем, почему одни программы работают быстрее, а другие медленнее.

Несколько простых наблюдений

• В задаче обмена двух чисел мы всегда делаем ровно три шага (без учёта ввода/вывода). То есть время выполнения не зависит от значений a и b. Это — константная сложность.
• В задаче с последовательностью мы выполняем приблизительно n одинаковых действий, если нужно n чисел. Это — линейная сложность.
• В задаче про Васю и прямоугольник всё сложнее: число операций сильно зависит от размеров сторон. В нашем «простом» решении были вложенные циклы (один цикл внутри другого), поэтому оно может работать очень медленно — это пример квадратичной или похожей на квадратичную сложности.

Что такое «сложность» простыми словами

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

Мы обычно пишем это в виде O(...) (читается: «большое-О»):

• O(1) — константа: всегда одинаково быстро.
• O(n) — линейно: время растёт примерно пропорционально n.
• O(n^2) — квадратично: время растёт примерно как n * n.
• O(log n) — логарифмически: очень быстрое уменьшение (например, делим задачу пополам на каждом шаге).

Не будем сейчас вдаваться в строгую математику — достаточно понимать идею: меньшая сложность = быстрее при больших данных.

Почему важно оптимизировать

Посмотрим на внутренний цикл из задачи с прямоугольником (тот, где мы отнимаем b от a много раз):

while a >= b:
    a -= b
    count += 1

Задача этого фрагмента — посчитать, сколько раз b помещается в a, и найти остаток. Но делать это циклом вычитаний — долго. Представь: a = 1000, b = 1 — нужно 1000 вычитаний. Если же у нас есть операции целочисленного деления и взятия остатка, то всё это делается за один шаг: count = a // b, a = a % b.

Пример на Python — оптимизированный вариант:

a = int(input("Введите длину a: "))
b = int(input("Введите ширину b: "))

while a * b > 1:
    count = a // b       # сколько квадратов размера b помещается в a
    a = a % b            # остаток — новая маленькая сторона
    print(count, b)
    a, b = b, a          # меняем стороны местами

Почему это лучше?

• Вместо тысячи вычитаний мы выполняем деление и находим остаток. Для чисел 1000 и 1 это одна операция вместо тысячи. Этот пример наглядно показывает, что правильный выбор операций сильно влияет на скорость.
• Мы перешли от большого количества шагов к небольшому, то есть снизили сложность. Подробнее об оценке сложности поговорим дальше.

Коротко о том, что запомнить

• Смотри на алгоритм не только по тому, что он делает, но и как часто он делает шаги при увеличении входных данных.
• Небольшое изменение в способе выполнения (например, замена многократного вычитания на деление) может дать огромный выигрыш в скорости.
• В курсе мы часто будем возвращаться к вопросам эффективности — но формальную теорию оставим для более продвинутого курса.