Полный перебор пар: вложенные циклы и границы сложности

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

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

Простой пример — вывести таблицу умножения.

for row in range(1, 6):
    for column in range(1, 6):
        print(row * column, end=' ')
    print()

Внешний цикл отвечает за строки, внутренний — за столбцы. После каждой строки вызывается print(), чтобы перейти на новую строку.

Перебор пар

В задачах часто нужно проверить все пары чисел. Чтобы не считать одну и ту же пару дважды, внутренний цикл начинают с i + 1.

numbers = [2, 8, 5, 11]
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 000, полный перебор пар станет слишком медленным. В таких случаях ищут другой прием: сортировку, словарь, множество, два указателя или предварительные суммы.

Как тренироваться

Начинайте с задач на таблицы и координаты. Затем переходите к парам чисел, поиску одинаковых элементов и простому перебору вариантов. Каждый раз задавайте вопрос: сколько проверок сделает программа?

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