3Суммирование

Если алгоритм содержит цикл (for, while), то время его работы является суммой времён отдельных шагов. Например, как мы знаем из раздела 1.2, выполнение j-ro шага алгоритма сортировки вставками требует времени, пропорционального. Поэтому общее время будет определяться суммой

п

которая есть 0(га2). Подобного рода суммы нам не раз встретятся (в частности, в главе 4 при анализе рекуррентных соотношений).

В разделе 3.1 перечислены основные свойства сумм. Некоторые из этих свойств доказываются в разделе 3.2; большинство пропущенных доказательств можно найти в учебниках по математическому анализу.

3.1. Суммы и их свойства

Для суммы а\ + (12 + ... + ап используют обозначение

п к=1

При п = 0 значение суммы считается равным 0. Как правило, нижний и верхний пределы суммирования - целые числа. (Если это не так, обычно подразумеваются целые части.) В конечных суммах слагаемые можно произвольно переставлять. В курсах анализа определяют сумму бесконечного ряда (series)

«1 + «2 + а3 + • • • ИЛИ

оо к=1

как предел последовательности частичных сумм

п

lim Уак.

к=1

Если предела не существует, говорят, что ряд расходится (diverges); в противном случае он сходится. Если ряд JfcLi \ак\ сходится, то ряд JfcLi ак называют абсолютно сходящимся (absolutely convergent series); всякий абсолютно сходящийся ряд сходится, но не наоборот. При перестановке членов абсолютно сходящегося ряда он остаётся абсолютно сходящимся и его сумма не меняется.

Линейность

Свойство линейности гласит, что

ппп

2{сак + Ьк) = сак + Ьк

к=1к=1к=1

для любого числа с и для любых конечных последовательностей <2i,..., ап и &i,..., Ьп. Почленно складывать и умножать на числа можно не только конечные суммы, но и сходящиеся бесконечные ряды.

Арифметические прогрессии

Сумма

п

/г=1 + 2+... + га,

к=1

которая возникла при анализе алгоритма сортировки вставками, является арифметической прогрессией (arithmetic series). Её значение равно

п

J2k=-n(n+l)=(3.1)

к=1

= в(п2).(3.2)

Геометрические прогрессии

При х ф 1 сумму геометрической прогрессии (geometric или exponential series)

п

хк = 1 + х + х2 + ... + х

к=0

можно найти по формуле

к=0

Сумма бесконечно убывающей геометрической прогрессии (при ж < 1) даётся формулой

оо fc=0

Гармонический ряд

имеет вид 1 + 1/2+1/3 + ...+ 1/га+...; его га-ая частичная сумма (rath harmonic number) равна

Нп = 1 + \+1- + ...+ А- = \ = \пп + 0(1). (3.5)

к=1

Почленное интегрирование и дифференцирование

Дифференцируя или интегрируя обе части известного тождества, можно получить новое. Например, дифференцируя тождество (3.4) и умножая результат на ж, получаем

оо

к=0V>

Суммы разностей

Для любой последовательности ао, а\,..., ап можно записать тождество

п

2(ак - afc-i) = ап- а0(3.7)

к=1

(все промежуточные члены сокращаются). Такие суммы по-английски называют telescoping series. Аналогично,

те -1

2(ак - ак+1) = а0

к=0