Алгоритмы - построение и анализ (1021735), страница 20
Текст из файла (страница 20)
Рост функций Задачи 3-1. Асимптотическое поведение полиномов Пусть р(п) представляет собой полипом степени с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) + Т ((и/21 ) + О (и) при п ) 1. Граничные условия — еще один пример технических особенностей, которые обычно игнорируются. Поскольку время работы алгоритма с входными данными фиксированного размера выражается константой, то в рекуррентных соотношениях, описывающих время работы алгоритмов, для достаточно малых и обычно справедливо соотношение Т (и) = О (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
