Ряды в анализе цикла: арифметический и геометрический

Коротко

Почти весь счёт циклов сводится к двум рядам (ряд - это сумма подряд идущих слагаемых). Арифметический - 1 + 2 + ... + n = n(n+1)/2, порядка n²/2: он выходит, когда работа на круге растёт равномерно. Геометрический - 1 + 2 + 4 + ... + 2ᵏ = 2^(k+1) - 1 при удвоении и 1 + 1/2 + 1/4 + ... < 2 при делении пополам: он выходит, когда работа множится или делится в разы. Свернуть ряд в формулу - и порядок цикла виден.

Если знаешь, что n + n/2 + n/4 + ... это Θ(n), а не Θ(n·log n), - листай до «Теперь сам».

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

rabota = n
while rabota >= 1:
    sdelat(rabota)      # стоит столько, сколько rabota
    rabota = rabota // 2

Кругов тут порядка log₂ n - примерно столько раз n делится пополам до единицы. Соблазн умножить: log n кругов по работе до n - значит n·log n? Нет. Работа на кругах не одинаковая, а падает вдвое: n + n/2 + n/4 + ... + 1. Такую сумму нельзя считать «число кругов × работа»: её надо сложить как ряд, и выйдет около 2n, то есть Θ(n), а не Θ(n·log n).

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

Арифметический ряд - лестница с равными ступенями: каждая на одну клетку выше прошлой, и всего клеток - половина прямоугольника. Геометрический - лестница, где каждая ступень вдвое выше (или ниже) прошлой: при удвоении последняя ступень почти равна всем предыдущим вместе, при делении пополам первая ступень почти равна всему остатку. Поэтому геометрическую сумму задаёт её самый большой член, а не число членов.

Механизм: два ряда и их суммы

Арифметический (разобран в главе про счёт операций): 1 + 2 + ... + n = n(n+1)/2, порядка n²/2. Складываешь ряд с собой задом наперёд - n столбиков по (n+1), пополам.

Геометрический при удвоении: 1 + 2 + 4 + ... + 2ᵏ = 2^(k+1) - 1. Почему: каждый член на единицу больше суммы всех предыдущих (1, потом 1+2=3=4-1, потом 1+2+4=7=8-1), поэтому вся сумма на единицу меньше следующей степенью двойки. Итог - порядка удвоенного последнего члена.

Геометрический при делении пополам: 1 + 1/2 + 1/4 + ... < 2. Сколько ни добавляй, сумма не переваливает за 2: каждый новый член закрывает половину оставшегося до двойки зазора. Поэтому n + n/2 + n/4 + ... < 2n - линия, а не n·log n.

Правило

Работа растёт равномерно на круге - это арифметический ряд, Θ(n²). Работа множится или делится в разы - это геометрический ряд, и его задаёт самый большой член: сумма при делении пополам меньше удвоенного первого, при удвоении - около удвоенного последнего. Складывать «число кругов × работу» можно, только если работа на кругах ОДИНАКОВА.

Разбор: половинки складываются в линию

Вернёмся к крючку. Работа идёт n, n/2, n/4, ..., 1 - это n·(1 + 1/2 + 1/4 + ...). Скобка меньше 2, значит вся сумма меньше 2n: Θ(n). Хотя кругов порядка log₂ n, время линейное, потому что почти вся работа приходится на первый круг, а хвост тает.

Возьми n = 1024. Пополам оно делится десять раз (log₂ 1024 = 10), поэтому работа идёт одиннадцатью слагаемыми - не забудь последнюю единицу: 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 2047, меньше двух n. Одиннадцать кругов, а множителя log n у линии нет: первый круг сделал больше половины всей работы, а последние - считанные единицы. Это и значит «сумма задаётся наибольшим членом». Типичная же ошибка - увидеть log n кругов и приписать множитель log n ко всему; множитель появляется, только если работа на кругах не убывает.

Разбор: удвоение массива стоит линию, а не квадрат

Динамический массив, когда заполняется, удваивает ёмкость и перекопирует содержимое: 1 элемент, потом 2, потом 4, ..., до n. Кажется, что перекопировок много и это дорого. Сложим их: 1 + 2 + 4 + ... + n = 2n - 1 (при n - степени двойки). Все перекопировки вместе стоят Θ(n) - меньше двух проходов по массиву. Поэтому добавление n элементов в динамический массив в сумме линейно, хотя отдельные добавления изредка дорогие. Ряд превратил «страшно много копирований» в «меньше двух проходов».

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

Главная ошибка - множить там, где надо складывать ряд. log n кругов с убывающей вдвое работой - это Θ(n), а не Θ(n·log n); log n кругов с растущей вдвое работой - Θ(n) тоже (геометрия), а не Θ(n·log n). Множитель log n появляется лишь тогда, когда на каждом из log n кругов работа ОДИНАКОВА и равна порядка n - вот тогда n·log n. Спутать эти случаи - значит завысить или занизить оценку в log n раз.

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

Геометрический ряд - основа «усреднённой» оценки: отдельная операция иногда дорогая, но в сумме за много операций выходит дёшево. Так считают динамический массив, построение кучи, удвоение буфера. Увидев «изредка перекопируем всё», не пугайся: сложи копирования как геометрический ряд, и почти всегда выйдет линия. Это отличает дорогую в среднем структуру от дешёвой.

Теперь сам

Посчитай две суммы: 1 + 2 + 4 + ... + 2¹⁰ и n + n/2 + n/4 + ... + 1 (границы - степени двойки). Какого порядка каждая?

Ответ. Первая - геометрический ряд при удвоении: 2^(10+1) - 1 = 2¹¹ - 1 = 2047, порядка удвоенного последнего члена 2¹⁰ = 1024. Вторая - геометрический ряд при делении: n·(1 + 1/2 + 1/4 + ...) < 2n, порядок Θ(n). Обе - линии от своего наибольшего члена, несмотря на то что членов в них порядка log.

Главное

Два ряда закрывают счёт циклов. Арифметический 1 + 2 + ... + n = n(n+1)/2 - Θ(n²), выходит при равномерном росте работы. Геометрический задаётся самым большим членом: при удвоении 1 + 2 + ... + 2ᵏ = 2^(k+1) - 1, при делении 1 + 1/2 + ... < 2, оба - Θ от наибольшего члена. Умножать «кругов × работу» можно только при ОДИНАКОВОЙ работе на кругах; при убывающей вдвое множителя log n нет.