Информатика · объяснение и практика

Как посчитать число действий вложенных циклов с зависимой границей

Считаем действия вложенных циклов с зависимой границей, выводим треугольную сумму и отличаем фактическое число итераций от числа уровней вложенности.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Переменные, ветвления, циклы и функции · Учебная карта

Главная мысль

Если внешний индекс i проходит 0…n−1, а внутренний j проходит 0…i−1, тело выполняется 0+1+…+(n−1) = n(n−1)/2 раз. Вложенность сама по себе не заменяет подсчёт границ.

Почему нельзя автоматически перемножить n на n

Для n = 4 внешний цикл имеет i = 0,1,2,3. При i = 0 внутренний цикл пуст, при 1 выполняется один раз, при 2 — два, при 3 — три. Всего 6 выполнений тела. Число 16 получилось бы для прямоугольной области, где внутренний цикл каждый раз проходит все четыре значения.

Треугольная область соответствует, например, сравнению каждой пары различных элементов один раз: выбирают j строго меньше i. Пары (0,1) и (1,0) не считаются двумя отдельными неупорядоченными парами, а сравнение элемента с самим собой исключено. Геометрия индексов помогает понять смысл формулы, а не только запомнить половину квадрата.

Как вывести сумму и проверить край

Сумма 0+1+…+(n−1) равна n(n−1)/2. Можно сложить её с записью в обратном порядке: каждая из n пар даёт n−1, затем разделить удвоенную сумму пополам. Для n = 1 получается 0, что соответствует отсутствию пары из одного элемента. Для n = 2 получается 1, единственная пара.

Если внутренний цикл включает j = i, число действий становится 1+2+…+n = n(n+1)/2. Изменение одного знака границы добавляет ровно n диагональных случаев, по одному на каждый внешний индекс. Асимптотический порядок остаётся квадратичным, но точный результат меняется. Поэтому одинаковое O(n²) не делает два алгоритма логически одинаковыми.

Пример

Сколько неупорядоченных пар разных элементов в списке из 6 элементов?

6·5/2 = 15. Это число выполнений цикла по всем j меньше i, если каждая пара обрабатывается один раз.

Почему два цикла не всегда дают квадрат

Если внутренний цикл всегда выполняет только три шага независимо от n, общая стоимость 3n линейна. Если внутренний цикл каждый раз удваивает индекс до n, число его шагов логарифмично, а общая стоимость может быть порядка n log n. Нужно читать обновление переменной и условие завершения, а не считать отступы в коде.

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

От чтения к действию

А теперь — вы

Внешний i = 0…4, внутренний j = 0…i−1. Сколько выполнений тела?

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

Два вложенных цикла всегда означают O(n²)?

Нет. Пределы, шаги и стоимость тела могут давать другой порядок.

Включение j = i меняет асимптотический порядок?

Для этой треугольной схемы нет, но добавляет n действий и меняет смысл обрабатываемых пар.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться