Вложенные циклы: откуда берётся n²

Если знаешь, почему 1+2+...+n = n(n+1)/2 и откуда у сортировки вставками квадрат - листай до «Теперь сам».

Как думаешь, сколько всего кругов

for i in range(n):
    for j in range(i):
        rabota()

Внутренний цикл зависит от внешнего: на круге i он делает i кругов. При i = 0 - ноль, при i = 1 - один, ... при i = n-1 - n-1. Значит всего rabota() выполнится 0 + 1 + 2 + ... + (n-1) раз, а не n·n. Соблазн сказать «два цикла - значит n²» ошибается ровно вдвое: настоящий ответ - около половины n².

На что это похоже

Нарисуй строки разной длины: первая пустая, вторая из одной клетки, третья из двух, и так до n-1 клеток в последней. Получится прямоугольный треугольник. Число клеток в нём - половина прямоугольника n × n, из которого его вырезали. Поэтому счёт вложенного цикла с растущей границей - это «половина квадрата», а не целый квадрат.

Механизм: почему сумма равна n(n+1)/2

Сложить 1 + 2 + ... + n в лоб - n действий. Но есть приём, из-за которого эта сумма и попадает в анализ так часто. Выпиши её дважды, второй раз задом наперёд, и сложи по столбикам:

  1  +   2  +   3  + ... +   n
  n  + (n-1)+ (n-2)+ ... +   1
-----------------------------------
(n+1)+ (n+1)+ (n+1)+ ... + (n+1)

В каждом столбике сумма одна и та же - n+1, а столбиков n. Значит удвоенная сумма равна n·(n+1), а сама сумма - n(n+1)/2. Деление на 2 здесь не случайность: мы сложили две копии, поэтому итог пополам. Формула точная, а не приблизительная: 1+2+3 = 6 и 3·4/2 = 6.

Отсюда и «половина n²»: n(n+1)/2 = n²/2 + n/2, и при большом n первое слагаемое больше второго.

Формула годится для любой верхней границы - подставь её вместо n. Ряд из крючка кончался не на n, а на n-1, и ноль в начале ничего не добавляет, поэтому 0 + 1 + ... + (n-1) = 1 + 2 + ... + (n-1) = (n-1)·n/2. Та же треугольная формула, только верхняя граница на единицу меньше.

Правило

Вложенный цикл, где внутренняя граница растёт вместе с внешней, даёт СУММУ, а не произведение. Ключевая сумма анализа - 1 + 2 + ... + m = m(m+1)/2; она порядка m²/2. Систематически сворачивать такие ряды научит глава про суммы; здесь достаточно этой одной.

Разбор: откуда квадрат у сортировки вставками

Сортировка вставками из прошлого раздела: внешний цикл берёт элемент a[j], внутренний сдвигает влево всех, кто больше ключа.

for j in range(1, n):
    key = a[j]
    i = j - 1
    while i >= 0 and a[i] > key:   # на круге j крутится до j раз
        a[i + 1] = a[i]
        i = i - 1
    a[i + 1] = key

Сколько раз крутится внутренний while, зависит от входа. Худший случай - список, отсортированный в обратном порядке: каждый новый элемент меньше всех левых, и его приходится тащить в самое начало. На круге j внутренний цикл делает j сдвигов, итого 1 + 2 + ... + (n-1) = n(n-1)/2 - квадрат. Лучший случай - список уже отсортирован: a[i] > key ложно сразу, внутренний цикл не делает ни круга, и всего работа линейная, n-1 проверок. Одна и та же программа: на одном входе - линия, на другом - квадрат.

Разбор: два цикла, а не квадрат

Не всякая вложенность квадратична - смотреть надо на число кругов, а не на отступы.

for i in range(n):
    for j in range(10):
        rabota()

Внутренний цикл всегда делает ровно 10 кругов - это константа, не зависящая от n. Всего 10·n вызовов, то есть линия с большим множителем, а не квадрат. Другой случай - внутренний цикл с досрочным break, который почти всегда рвётся на первом же круге: отступ есть, а второго множителя n нет. Квадрат даёт именно РАСТУЩАЯ вместе с n внутренняя граница.

Что ломается без этого

Правило «две вложенные петли - это n²» подводит в обе стороны. В одну - когда внутренний цикл ограничен константой или рвётся рано: код линейный, а его записывают в квадратичные и зря переписывают. В другую - когда квадрат прячется без всякой вложенности: for x in a: if x in b: выглядит как один цикл, но in по списку - это второй, и суммарно снова n². Считать надо круги, а не глубину отступа.

Зачем это в работе

Треугольную сумму узнают в лицо: как только на круге i работа пропорциональна i (обрабатываем «всех предыдущих», «все пары слева», «хвост, который ещё не разобрали»), суммарная цена - порядка n²/2. Это первый признак, что алгоритм переборный и на большом входе его придётся менять - о чём и будет половина курса.

Теперь сам

Сколько раз выполнится rabota()? И линейно это или квадратично?

for i in range(n):
    for j in range(i, n):
        rabota()