2.2 СУММЫ И РЕКУРРЕНТНОСТИ

Итак, мы разобрались, как выражать суммы с помощью того или иного причудливого обозначения. Но как надо действовать для нахождения значения той или иной суммы? Один из способов — заметить, что существует тесная связь между суммами и рекуррентностями. Сумма

эквивалентна рекуррентности

Следовательно, можно вычислять суммы в замкнутой форме, используя для этого методы решения рекуррентных соотношений в замкнутой форме, которые изучались в гл. 1.

К примеру, если есть некая постоянная плюс некое кратное то сигма-рекуррентность (2.6) приобретает следующий общий вид:

Действуя так же, как в гл. 1, мы находим, что а вообще искомое решение может быть записано в виде

где коэффициенты при основных параметрах и у.

Репертуарный метод подсказывает попробовать подставить вместо простые функции от в надежде найти такие постоянные параметры и у, при которых решение особенно просто. Подстановка дает откуда

Подстановка дает откуда

А подстановка дает откуда

и мы получаем Просто как дважды два.

Итак, если мы хотим вычислить сумму

то сигма-рекуррентность (2.6) сводится к и ответом будет

И обратно, многие рекуррентности могут быть сведены к суммам; в силу этого специальные методы вычисления сумм, которые мы изучим позже в этой главе, будут полезны и при решении рекуррентных соотношений, справиться с которыми иначе было бы трудно. Подходящий пример — рекуррентность, связанная с задачей о ханойской башне:

Ее можно привести к частному случаю (2.6), если поделить обе части на

Теперь можно положить получая

Отсюда вытекает, что

(Обратите внимание, что член с не включен в эту сумму.) Сумма геометрической прогрессии будет выведена в этой главе позднее — она окажется равной Следовательно,

В этом выводе мы перешли от заметив, что исходное рекуррентное соотношение можно было поделить на Эта уловка — частный случай общего метода, с помощью которого фактически любую рекуррентность вида

можно свести к сумме. Суть данного метода состоит в том, чтобы домножить обе части на суммирующий множитель

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

Следовательно,

и решением исходной рекуррентности (2.9) является

Например, при мы получаем

Но хватит ли нам сообразительности, чтобы найти требуемое Нет проблем: достаточно развернуть соотношение

, чтобы выяснить, что искомым суммирующим множителем является дробь

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

Как всегда, надо соблюдать осторожность, чтобы не поделить на нуль. Метод суммирующего множителя срабатывает всегда, когда все а и все не равны нулю.

Применим эти соотношения к рекуррентности, которая возникает в связи с анализом „быстрой сортировки" — одного из наиболее популярных методов внутренней сортировки данных в компьютере. Среднее число выполняемых „быстрой сортировкой" шагов сравнения, когда она применяется к элементам данных, расположенным в случайном порядке, удовлетворяет рекуррентному соотношению

Это выглядит гораздо страшнее, чем встречавшиеся до сих пор рекуррентности: сюда входит сумма всех предыдущих величин, да еще деление на Попытка вычислить несколько первых значений даст нам кое-какую информацию но не избавит от чувства страха.

Однако сложность соотношения (2.12) можно снижать постепенно, сперва избавившись от деления, а затем — от знака . Реализуя эту идею, домножим обе части рекуррентности на получив соотношение

а если заменим на то

Теперь можно вычесть второе равенство из первого, и знак пропадает:

Между прочим, это соотношение справедливо и при поскольку . Итак, исходное рекуррентное соотношение для сводится к гораздо более простому:

Явный прогресс. Теперь мы в состоянии подключить к делу суммирующий множитель, поскольку полученное рекуррентное соотношение имеет вид (2.9) с Общий метод, изложенный на предыдущей странице, подсказывает нам, что нужно домножить все рекуррентное соотношение на нечто, кратное величине

Тогда, согласно (2.10), решением является

Оставшаяся сумма очень похожа на величину, которая часто возникает в приложениях. В действительности она возникает столь часто, что заслуживает специального названия и специального обозначения:

Буква Н происходит от слова «harmonic» так что — это гармоническое число. Оно названо так потому, что гармоника, извлекаемая из скрипичной струны, - это основной тон, производимый струной длиной от длины исходной струны.

Изучение „быстрой сортировки" — рекуррентности (2.12) — можно завершить приведением к замкнутому виду, если мы сможем выразить через Сумма в нашей формуле для есть

Ее можно без особого труда связать с суммой заменив к на и изменив граничные условия:

Полный порядок! Найдена сумма, необходимая для завершения решения (2.12): среднее число выполняемых «быстрой сортировкой» сравнений, когда она применяется к случайно расположенным элементам данных, есть

И, как водится, убедимся в правильности первых значений: