Логарифм в сумме: гармонический ряд

Коротко

Сумма 1 + 1/2 + 1/3 + ... + 1/n называется гармоническим рядом Hₙ. Она не сходится к числу (в отличие от 1 + 1/2 + 1/4) и не растёт линейно - она растёт как ln n. Отсюда логарифм появляется в оценках, где на шаге i работа пропорциональна 1/i. Основание логарифма в Θ роли не играет: log₂ n и ln n отличаются лишь постоянным множителем.

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

Как думаешь, к чему сходится

1 + 1/2 + 1/3 + 1/4 + ... + 1/n

Члены тают, как в геометрическом ряду 1 + 1/2 + 1/4, который не переваливал за 2. Значит и этот сходится к какому-то числу? Нет. Разница в скорости, с которой члены тают: там каждый был вдвое меньше прошлого, здесь - лишь чуть меньше (1/3 против 1/2). Такого убывания не хватает, чтобы сумма остановилась: она растёт без предела, но очень медленно - как ln n.

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

Представь, что закрашиваешь площадь столбиками ширины 1 и высоты 1/k: первый высотой 1, второй 1/2, третий 1/3. Столбики всё ниже, но никогда не нулевые, поэтому закрашенная площадь всё растёт. Огибающая этих столбиков - кривая 1/x, а площадь под 1/x от 1 до n - это в точности ln n. Вот почему сумма ведёт себя как логарифм: она повторяет площадь под 1/x.

Механизм: почему именно логарифм

Гармонический ряд Hₙ = 1 + 1/2 + ... + 1/n равен ln n с точностью до небольшой добавки: Hₙ = ln n + O(1). Причина - в предыдущей картинке: сумма столбиков высоты 1/k зажата вокруг площади под кривой 1/x, а эта площадь от 1 до n и есть натуральный логарифм ln n - так ln и определяют: как площадь под 1/x. Вот почему в ответе именно логарифм, а не что-то другое. Геометрический ряд 1/2ᵏ сходится, потому что его члены тают в РАЗЫ; гармонический 1/k расходится, потому что его члены тают лишь на доли - медленнее, чем нужно для остановки, но достаточно медленно, чтобы рост был логарифмическим, а не линейным.

Основание логарифма в Θ неважно. log₂ n (по основанию 2) и ln n (по основанию e) отличаются постоянным множителем: ln n = log₂ n · ln 2 ≈ 0,69·log₂ n. Смена основания - это умножение на константу, а константу Θ выбрасывает. Поэтому пишут просто log n, не указывая основание, - в порядке роста оно не меняет ничего. Основание важно лишь в точном счёте с константами.

Правило

1 + 1/2 + ... + 1/n = Hₙ = Θ(log n). Сумма обратных чисел - это логарифм, а не константа и не линия. Основание логарифма в оценке порядка не указывают: любые два отличаются постоянным множителем.

Разбор: откуда берётся n·log n

Пусть на шаге i (от 1 до n) алгоритм просматривает каждый i-й элемент массива, то есть делает n/i работы:

i=1: n    i=2: n/2    i=3: n/3    ...    i=n: 1

Сложим: n/1 + n/2 + ... + n/n = n·(1 + 1/2 + ... + 1/n) = n·Hₙ. Гармоническая сумма это Θ(log n), значит всё вместе - Θ(n·log n). Так n·log n вырастает не только из «делим пополам log n раз», но и из гармонического ряда: n вынесли, скобка дала логарифм.

В числах гармоническая сумма и правда еле растёт. H₁₀ ≈ 2,9, H₁₀₀ ≈ 5,2, H₁₀₀₀ ≈ 7,5: вход вырос в сто раз, а сумма - меньше чем втрое. Именно так ведёт себя логарифм: ln 1000 ≈ 6,9, и добавка O(1) между Hₙ и ln n держится около 0,58 при любом n. Ни константа (сумма всё же растёт), ни линия (росла бы в сто раз) - ровно логарифм.

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

Один алгоритм делит задачу на 2 части (log₂ n уровней), другой на 10 (log₁₀ n уровней). Уровней у второго меньше - но log₁₀ n = log₂ n / log₂ 10 ≈ log₂ n / 3,32, то есть ровно втрое с небольшим меньше. Это постоянный множитель: оба - Θ(log n). На выбор «какой алгоритм» основание влияет через константу (меньше уровней - быстрее на практике), на класс сложности - нет. Поэтому в O(log n) основание и не пишут.

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

Две ошибки. Первая - решить, что гармонический ряд сходится, как геометрический: 1/k и 1/2ᵏ тают по-разному, первый уходит в бесконечность (медленно), второй останавливается. Вторая - спорить об основании логарифма в оценке порядка: O(log₂ n) и O(ln n) - одно и то же, разница лишь в невидимой для Θ константе. Указание основания в асимптотике выдаёт непонимание, что константу уже выбросили.

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

Гармонический ряд - вторая дорога к n·log n помимо «деления пополам». Он всплывает там, где работа на шаге обратно пропорциональна номеру шага: разбор некоторых версий быстрой сортировки, оценки «сколько в среднем сравнений», вероятностные подсчёты. Узнав в сумме 1 + 1/2 + ... + 1/n, сразу пишешь Θ(log n) и не пытаешься свернуть её в константу.

Теперь сам

Какого порядка сумма n/1 + n/2 + n/3 + ... + n/n? А 1 + 1/2 + ... + 1/n отдельно?

Ответ. Вынеси n за скобку: n·(1 + 1/2 + ... + 1/n) = n·Hₙ. Скобка - гармонический ряд, это Θ(log n), поэтому вся сумма - Θ(n·log n). Сам гармонический ряд 1 + 1/2 + ... + 1/n - Θ(log n): он растёт без предела, но логарифмически, повторяя площадь под 1/x.

Главное

Гармонический ряд 1 + 1/2 + ... + 1/n = Hₙ = Θ(log n) - не константа и не линия: члены 1/k тают слишком медленно, чтобы сумма сошлась, но достаточно медленно, чтобы рост был логарифмическим (сумма повторяет площадь под 1/x, а это ln n). Основание логарифма в Θ не пишут: log₂ n и ln n отличаются постоянным множителем. Гармонический ряд - вторая дорога к n·log n: n/1 + n/2 + ... = n·Hₙ.