Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
2.2 СУММЫ И РЕКУРРЕНТНОСТИИтак, мы разобрались, как выражать суммы с помощью того или иного причудливого обозначения. Но как надо действовать для нахождения значения той или иной суммы? Один из способов — заметить, что существует тесная связь между суммами и рекуррентностями. Сумма
эквивалентна рекуррентности
Следовательно, можно вычислять суммы в замкнутой форме, используя для этого методы решения рекуррентных соотношений в замкнутой форме, которые изучались в гл. 1. К примеру, если
Действуя так же, как в гл. 1, мы находим, что
где Репертуарный метод подсказывает попробовать подставить вместо
Подстановка
А подстановка
и мы получаем Итак, если мы хотим вычислить сумму
то сигма-рекуррентность (2.6) сводится к И обратно, многие рекуррентности могут быть сведены к суммам; в силу этого специальные методы вычисления сумм, которые мы изучим позже в этой главе, будут полезны и при решении рекуррентных соотношений, справиться с которыми иначе было бы трудно. Подходящий пример — рекуррентность, связанная с задачей о ханойской башне:
Ее можно привести к частному случаю (2.6), если поделить обе части на
Теперь можно положить
Отсюда вытекает, что
(Обратите внимание, что член с В этом выводе мы перешли от
можно свести к сумме. Суть данного метода состоит в том, чтобы домножить обе части на суммирующий множитель
При этом множитель
Следовательно,
и решением исходной рекуррентности (2.9) является
Например, при Но хватит ли нам сообразительности, чтобы найти требуемое
или любое подходящее кратное этой величины. В частности, для рекуррентности, связанной с задачей о ханойской башне, Как всегда, надо соблюдать осторожность, чтобы не поделить на нуль. Метод суммирующего множителя срабатывает всегда, когда все а и все Применим эти соотношения к рекуррентности, которая возникает в связи с анализом „быстрой сортировки" — одного из наиболее популярных методов внутренней сортировки данных в компьютере. Среднее число выполняемых „быстрой сортировкой" шагов сравнения, когда она применяется к
Однако сложность соотношения (2.12) можно снижать постепенно, сперва избавившись от деления, а затем — от знака
а если заменим
Теперь можно вычесть второе равенство из первого, и знак
Между прочим, это соотношение справедливо и при
Явный прогресс. Теперь мы в состоянии подключить к делу суммирующий множитель, поскольку полученное рекуррентное соотношение имеет вид (2.9) с
Тогда, согласно (2.10), решением является
Оставшаяся сумма очень похожа на величину, которая часто возникает в приложениях. В действительности она возникает столь часто, что заслуживает специального названия и специального обозначения:
Буква Н происходит от слова «harmonic» так что Изучение „быстрой сортировки" — рекуррентности (2.12) — можно завершить приведением
Ее можно без особого труда связать с суммой
Полный порядок! Найдена сумма, необходимая для завершения решения (2.12): среднее число выполняемых «быстрой сортировкой» сравнений, когда она применяется к
И, как водится, убедимся в правильности первых значений:
|
1 |
Оглавление
|