Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 21
Текст из файла (страница 21)
Числа Фибоначчи Числа Фибоначчи определяются с помощью следующего рекуррентиого соотношения: Го = О, Е, = 1, Рг = Р; г+ Гг з, г > 2. (3.21) Таким образом, числа Фибоначчи образуют последовательность, в которой каждое очередное число представляет собой сумму двух предыдущих: О, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, Обозначение !к* и (читается как "логарифм со звездочкой от и") будет применяться для указания повторно применяемого логарифма, который определяется следующим образом.
Пусть 18(г! и представляет собой итерацию функции Г" (и) = = 18 и. Поскольку логарифм от неотрицательных чисел не определен, то функция 180! п определена, только если 18(г ~! гг > О. Не перепугайте обозначения 18(г! гг (логарифм, примененный последовательно г раз к аргументу и) и 1бг и (логарифм и, возведенный в г-ую степень). Итерированный логарифм определяется следующим образом: Часть 1.
Основы 104 Числа Фибоначчи тесно связаны с золоюиым сечением ф и сопряженным значе- нием Ф, которые задаются следующими формулами: = 1.б1803... 2 = — 0.51803 .. 2 (3.22) В частности, справедливо такое соотношение: Ф' — Ф Р;= (3.23) Упражнения 3.2-1. Покажите, что если функции / (и) и д (и) — монотонно неубывающие, то функции /(и) + д(п) и /(д(п)) также монотонно неубывающие. Кроме того, если к тому же функции /(и) и д (и) — неотрицательные, то монотонно неубывающей является также функция / (и) . д (и).
3.2-2. Докажите уравнение (3.15). 3.2-3. Докажите уравнение (3.18). Кроме того, докажите, что кй = ы (2") и и1 = = о(п"). * 3.2-4. Является ли функция (18 п1! полиномиально ограниченной? Является ли полиномиально ограниченной функция (18 18 п1? *3.2-5. Какая из функций является асимптотически ббльшей: 18(18*п) или 18* (18 и)? 3.2-6. Докажите методом математической индукции, что 1-е число Фибоначчи удовлетворяет следующему равенству: Ф' — Ф' Г;= где Ф вЂ” золотое сечение, а Ф вЂ” его сопряженное. 327.
Докажите, что при 1 > 0 (4+ 2)-ое число Фибоначчи удовлетворяет неравенству Г; ~з ) Ф1. которое можно доказать методом индукции (см. упражнение 3.2-6). Поскольку Г 4( < 1, то выполняются неравенства )Ф')/~/5 < 1/~/5 < 1/2. Таким образом, г'-е число Фибоначчи Г, равно Ф'/~/5, округленному до ближайшего целого числа. Следовательно, числа Фибоначчи возрастают как показательная функция. 105 Глава 3. Рост функций Задачи 3-1.
Асимптотическое поведение полиномов Пусть р(п) представляет собой полипом степени с1 отп: Н р(п) = ,') а;п', '=о где аа > О, и пусть й — некоторая константа. Докажите с помощью определения асимптотических обозначений приведенные ниже свойства. а) Если 1о > д, то р (п) = О (п~). б) Если /с < с1, то р (п) = П (и"). в) Если к = с1, то р (и) = 9 (пь). г) Если /с > Н, то р (п) = о (п~). д) Если Й < д, то р (п) = м (п~). 3-2. Сравнение скорости асимптотического роста Для каждой пары (А, В) приведенных в таблице выражений укажите, в каком отношении А находится по отношению к В: О, о, П, ~о или О.
Предполагается, что 1о, е и с — константы, причем 1 > 1, е > О и с > > 1. Ответ должен быть представлен в виде таблицы, в каждой ячейке которой следует указать значения "да" или "нет". в. д. 3-3. Упорядочение по скорости асимптотического роста а) Расположите приведенные ниже функции по скорости их асимптотического роста, т.е. постройте такую последовательность функций дп дз,..., дзо, что д1 = й (дз), дз = й (дз), °, даа = й (дзо).
Разбейте список на классы эквивалентности, в которых функции 1 (п) и д (п) принадлежат одному и тому же классу тогда и только тогда, когда Г (п) = 9 (д (п) ). 106 Часть 1. Основы (~/2) 2 21я п 3 1б и (1 )1яп 2'~21я" 1к (1я' и) п2 и! (1й п)! (3/2)" 1б (п~) 22" п111ап 1п1пп и 2" п1Я1Я" 1пп 1 2'Я" е" 41к" (п+ 1)' ~(~~п 1к' (1я и) и 2п п1б и 22"+ б) Приведите пример неотрицательной функции г" (и), такой что ни для одной из представленных в задании а) функций д; (и) функция Г' (и) не принадлежит ни множеству 0 (д; (п)), ни множеству й (д; (и)). а) Из 1 (и) = 0(д(п)) следует д(п) = 0(1 (и)).
б) г" (и) + д (и) = О (плп ( 1' (и), д (и) ) ). в) Из г" (и) = 0 (д (и) ) следует 1я (г" (и) ) = 0 (1к (д (и) ) ), где при достаточно больших и 1к (д (и)) > 1 и Г" (и) > 1. г) Из г" (и) = 0(д(п)) следует 2П"1 = 0 (22о11). д) г" (и) = 0 ((г (и)) ). е) Из г" (и) = 0(д(п)) следуетд(п) = й(г'(и)). ж) г" (и) = 6 (г" (и/2) ). з) Г (и) + о (1 (и)) = О (1 (и)). 3-5.
Вариации в определениях 0 и й Определения й некоторых авторов несколько отличаются от нашего; в качестве обозначения этих альтернативных определений мы будем использовать символ й (читается "й бесконечность"). Говорят, что 1 (и) = й(д(п)), если существует положительная константа с, такая что ,г' (и) > сд (и) > 0 для бесконечно большого количества целых и. а) Покажите, что для любых двух асимптотически неотрицательных функций Г' (и) и д(п) выполняется одно из соотношений Г' (и) = = 0(д(п)) или г" (и) = й (д(п)) (или оба), в то время как при использовании й вместо й это утверждение оказывается ложным.
б) Опишите потенциальные преимущества и недостатки использования й вместо й для характеристики времени работы программы. 3-4. Свойства асимптотических обозначений Пусть У (и) и д (и) — асимптотически положительные функции. Докажите или опровергните справедливость каждого из приведенных ниже утверждений. Глава 3. Рост функций 107 Определения 0 некоторых авторов несколько отличаются от нашего; в качестве обозначения этих альтернативных определений мы будем использовать символ 0'. Говорят, что г" (и) = О' (д (и)) тогда и только тогда, когда ~~ (и) ~ = 0 (д (и)). в) Что произойдет, если теорему 3.1 перефразировать таким образом, что вместо 0 подставить 0', а й оставить без изменений? Некоторые авторы определяют 0 (читается "о с гильдой") для обозначения О, в котором игнорируются логарифмические множители: Г' (и): существуют положительные константы 0(д(п)) = с, й и по, такие что О < Г" (и) < сд(п)1б~(п) для всех п > по Дайте аналогичные определения й и О.
Докажите для них аналог теоремы 3.1. 3-6. Итерированные функции Оператор итераций ', использующийся в функции 1к', можно применять к любой монотонно неубывающей функции г" (и), определенной на множестве действительных чисел. Для данной константы с Е К итерированная функция Д определяется как ,гс (и) = пйп ) 1 > 0: ~1й (и) < с), где функция г б1 (и) должна быль корректно определена для всех г. Другими словами, величина Гс (и) — это функция Г", последовательно применяющаяся столько раз, сколько это необходимо для уменьшения аргумента до значения, не превышающего с. Для каждой из приведенных ниже функций Г" (и) и констант с дайте максимально точную оценку функции ~; (и).
в. 108 Часть 1. Основы Заключительные замечания Кнут (КпшЬ) [182] попытался выяснить происхождение О-обозначений и обнаружил, что впервые они появились в 1892 году в учебнике Бахманна (Р. ВасЬ- шапп) по теории чисел. О-обозначения были введены в 1909 году Ландау (Е. (.апдаи) при обсуждении распределения простых чисел. Введение й- и О-обозначений приписываются Кнуту [186], который исправил неточность популярного в литературе, но технически неаккуратного применения О-обозначений как для верхней, так и для нижней асимптотических границ. Многие продолжают использовать О- обозначения там, где более уместны были бы О-обозначения. Дальнейшее обсуждение исторического развития асимптотических обозначений можно найти у Кнута [182, 186], а также Брассарда (Вгаьаап)) и Брейтли (Вга!1еу) [46].
Определения асимптотических обозначений у разных авторов иногда различаются, однако в большинстве часто встречающихся ситуаций они дают согласующиеся результаты. В некоторых альтернативных случаях подразумевается, что функции не являются асимптотически неотрицательными, поэтому ограничению подлежит их абсолютное значение. Равенство (3.19) было получено Роббинсом (КоЬЬ!пз) [260]. Другие свойства элементарных математических функций можно найти в любом хорошем справочнике по математике, например, справочнике Абрамовича (АЬгагпоттйсЬ) и Стеган (81ейип) [ ! ] или Цвиллингера (Хтт!11!пйег) [320], а также в книгах по вычислительной математике, таких как книги Апостола (Аров!о!) [18] или Томаса (ТЬошаз) и Финик (Р!ппеу) [296].
В книге Кнута [182], а также Грехема (ОгаЬаш), Кнута и Паташника (Ра1ааЬпй) [!32] содержится множество материала по дискретной математике, который используется в информатике. ГЛАВА 4 Рекуррентные соотношения Как было сказано в главе 2, если алгоритм рекуррентно вызывает сам себя, время его работы часто можно описать с помощью рекуррентного соотношения. Рекурренп1ное сооиисогиение (гесиггепсе) — это уравнение или неравенство, описывающее функцию с использованием ее самой, но только с меньшими аргументами.
Например, мы узнали, что время работы процедуры Мекпл Яокт Т (и) в самом неблагоприятном случае описывается с помощью следующего рекуррентного соотношения: О (1) при и = 1, Т(п) = 2Т (и/2) + О (п) при п > 1. (4.1) Т (и) = аТ (п(Ь) + 1 (и), где а > 1, Ь > 1, а функция г' (п) — это заданная функция; для применения этого метода необходимо запомнить три различных случая, но после этого определение Решением этого соотношения является функция Т(п) = О (п1яп).
В настоящей главе вниманию читателя предлагаются три метода решения рекуррентных уравнений, т.е. получения асимптотических О- и О-оценок решения. В меюиоде подспвановок (ацЬзйюсюп ше1йос$) нужно догадаться, какой вид имеют граничные функции, а затем с помощью метода математической индукции доказать, что догадка правильная.
В меюлоде деревьев рекурсии (гесцгзюл-1гее шецзод) рекуррентное соотношение преобразуется в дерево, узлы которого представляют время выполнения каждого уровня рекурсии; затем для решения соотношения используется метод оценки сумм. В основнам методе (шаз1ег шейоб) граничные оценки решений рекуррентных соотношений представляются в таком виде: 110 Часть 1. Основы асимптотических границ во многих простых рекуррентных соотношениях стано- вится очень простым. Технические детали На практике в процессе формулировки и решения рекуррентных соотношений определенные технические моменты опускаются. Так, например, есть одна особенность, о которой часто умалчивают, — это допущение о том, что аргумент функции является целочисленным.
Обычно время работы Т(п) алгоритма определено лишь для целочисленных и, поскольку в большинстве алгоритмов количество входных элементов выражается целым числом. Например, рекуррентное соотношение, описывающее время работы процедуры МЕКОЕ БОКТ в наихудшем случае, на самом деле записывается так: Т (п) = О (1) при п = 1, (4.2) Т ((и/21) + Т ((и/2) ) + О (и) при п ) 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
