Конспект: суммы и логарифмы

Понятия

Арифметический ряд - 1 + 2 + ... + n = n(n+1)/2, порядок Θ(n²). Выходит при равномерном росте работы на круге.

Геометрический ряд - задаётся наибольшим членом. При удвоении 1 + 2 + ... + 2ᵏ = 2^(k+1) - 1 (Θ от последнего члена); при делении 1 + 1/2 + 1/4 + ... < 2 (Θ от первого). Оба линейны от своего максимума.

Гармонический ряд - 1 + 1/2 + ... + 1/n = Hₙ = Θ(log n). Расходится, но логарифмически: повторяет площадь под 1/x, а это ln n.

Оценка интегралом - для монотонной f сумма Σ f(k) того же порядка, что ∫ f(x)dx. Площадь под xᵏ до n равна n^(k+1)/(k+1).

Что унести

Умножать «кругов × работу» можно, только если работа на кругах ОДИНАКОВА. Если она множится или делится в разы - это геометрический ряд, и множителя log n в нём нет: n + n/2 + n/4 + ... = Θ(n).

Гармонический ряд - вторая дорога к n·log n помимо деления пополам: n/1 + n/2 + ... + n/n = n·Hₙ = Θ(n·log n).

Основание логарифма в Θ не пишут: log₂ n = ln n / ln 2, разница - постоянный множитель, а его Θ выбрасывает.

Что не сворачивается парным приёмом - оценивают интегралом. Растущая f: Σₖ₌ₘⁿ f(k) ≤ ∫ₘ^(n+1) f(x)dx. Правило для степеней: степень поднять на единицу, поделить на новую. Так Σk² = Θ(n³), Σk³ = Θ(n⁴).

Динамический массив, куча, удвоение буфера считаются геометрическим рядом: отдельная операция изредка дорога, а в сумме за n операций - линия.

Ловушки джокера

Умножил вместо сложения ряда. log n кругов с убывающей вдвое работой - это Θ(n), а не Θ(n·log n). Множитель log n появляется, лишь когда работа на кругах одинакова.

Решил, что гармонический ряд сходится. 1/k и 1/2ᵏ тают по-разному: геометрический останавливается, гармонический уходит в бесконечность (медленно, как log n).

Указал основание логарифма в асимптотике. O(log₂ n) и O(ln n) - одно и то же; писать основание значит не понимать, что константу уже выбросили.

Оценил интегралом немонотонную функцию. Метод требует, чтобы f везде росла или везде падала; иначе столбики не зажаты площадью с одной стороны.

Принял n³/3 за точную сумму квадратов. Интеграл даёт порядок, а не значение: точная сумма n(n+1)(2n+1)/6, у неё другой хвост.

Проверь себя

Когда счёт цикла - арифметический ряд, а когда геометрический, и чем их суммы отличаются по порядку?

Почему n + n/2 + n/4 + ... это Θ(n), а не Θ(n·log n)?

Почему гармонический ряд расходится, а 1 + 1/2 + 1/4 - нет?

Почему основание логарифма в Θ не важно?

Как оценить Σ k² интегралом и почему получается именно n³?