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

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

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

Если программа один раз проходит по списку из 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, словарь, сортировка или предварительные суммы.

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

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