Ограничения задачи и сложность алгоритма: пройдёт ли решение тесты

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

Сложность алгоритма показывает, как быстро растет время работы программы при увеличении входных данных. В школьных задачах это помогает понять, почему одно решение проходит…

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

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

Пример линейного решения

Нужно посчитать сумму чисел.

numbers = [1, 4, 7, 10]
total = 0

for number in numbers:
    total += number

print(total)

Каждое число обрабатывается один раз. Если чисел станет в десять раз больше, действий тоже станет примерно в десять раз больше.

Пример квадратичного решения

Нужно проверить все пары чисел.

numbers = [1, 4, 7, 10]
count = 0

for i in range(len(numbers)):
    for j in range(i + 1, len(numbers)):
        if numbers[i] + numbers[j] > 10:
            count += 1

print(count)

Здесь количество проверок растет намного быстрее. Для 100 элементов пар около 5 тысяч, а для 10 000 элементов — уже десятки миллионов.

Как выбирать решение на экзамене

Смотрите на ограничения. Если в задаче может быть 100 элементов, двойной цикл часто допустим. Если элементов 100 000, нужен более быстрый прием: один проход, множество set, словарь, сортировка или предварительные суммы.

Сложность не требует сложной математики на старте. Достаточно задавать вопрос: сколько раз программа обрабатывает каждый элемент? Один раз, несколько раз или для каждого элемента перебирает все остальные?

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

Практикум: оценка решения при n = 100000

Рассмотрите три алгоритма для 100000 элементов: один проход, сортировка и сравнение каждой пары. Не запускайте их сразу — сначала оцените порядок числа операций: около n, n log n и n². Подставьте величину и объясните, почему последний вариант может не завершиться вовремя. Затем измерьте первые два на одинаковом наборе без печати внутри замеряемого участка. Повторите запуск несколько раз и сравните медиану, а не единичный случай. Зафиксируйте также память и необходимость сохранять данные.

Контрольная точка

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

Частые вопросы

Нужно ли школьнику точно считать машинные операции?

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