Алгоритмы - построение и анализ (1021735), страница 18
Текст из файла (страница 18)
Асимптотические обозначения в уравнениях и неравенствах Мы уже видели, как асимптотические обозначения используются в математических формулах. Например, при введении О-обозначения мы писали "и = = О (пэ)". Можно также написать 2пз + Зп + 1 = 2иэ + 6 (и). Как же интерпретируются подобные формулы? Если в правой части уравнения (или неравенства) находится только асимптотическое обозначение, как в случае уравнения п = О (пэ), то знак равенства используется для указания принадлежности множеству: п е О (ссз).
Однако если аснмптотические обозначения встречаются в формуле в другой ситуации, они рассматриваются как подставляемые взамен некоторой неизвестной функции, имя которой не имеет значения. Например, формула 2пя + Зп+ 1 = 2ссз + О (и) означает, что 2пэ+ Зи+ 1 = 2пз+ г" (и), где г" (и) — некоторая функция из множества О (п). В данном случае функция ~ (п) = Зп+1, и она действительно принадлежит множеству 9 (и).
Подобное использование асимптотических обозначений позволяет избежать несущественных деталей и неразберихи в уравнениях. Например, в главе 2 время работы алгоритма сортировки методом слияния в наихудшем случае было Часть Е Основы 94 выражено в виде рекуррентного уравнения Т(п) = 2Т(п/2) + 6(п) . Если нас интересует только асимптотическое поведение Т(п), то нет смысла точно выписывать все слагаемые низших поркдков; подразумевается, что все они включены в безымянную функцию, обозначенную как 6 (и). Предполагается, что таких функций в выражении столько, сколько раз в нем встречаются асимптотические обозначения.
Например, в выражении 2," О (1) имеется только одна функция без имени (аргументом которой является г). Таким образом, это выражение — не одно и то же, что и О (1) + О (2) + + О (и), которое действительно не имеет однозначной интерпретации. Иногда асимптотические обозначения появляются в левой части уравнения, как, например, в таком случае: 2пз + 6 (и) = О (пз) .
Подобные уравнения интерпретируются в соответствии с таким правилом: при любаи выборе безымянньп функций, подставляемых вместо асимптотических обозначений в левую часть уравнения, можно выбрать и подставить в правую часть такие безымянные функции, что уравнение будет правильным. Таким образом, смысл приведенного выше уравнения в том, что для любой функции г" (и) Е О (и) существует некоторая функция д(п) е 6 (и ), такая что 2п + з (и) = д(п) для всех и. Другими словами, правая часть уравнения предоставляет меньший уровень детализации, чем левая. Несколько таких соотношений могут быть объединены в цепочку, например: 2п'+Зп+1=2п'+6(п) =6(п').
При этом каждое уравнение можно интерпретировать в соответствии со сформулированным выше правилом. Согласно первому уравнению, существует некоторая функция г (и) Е 6 (и), такая что для всех и выполняется соотношение 2пз + Зп + 1 = 2пз + у (и). Согласно второму уравнению, для любой функции д (и) е 6 (п) существует некоторая функция л(п) е О (пз), такая что для всех и выполняется соотношение 2пз + д(п) = й(п).
Заметим, что такая интерпретация подразумевает выполнение соотношения 2пз + Зп + 1 = 6 (пз), которое согласуется с нашими интуитивными представлениями о цепочке уравнений. о-обозначения Верхняя асимптотическая граница, предоставляемая О-обозначениями, может описывать асимптотическое поведение функции с разной точностью. Граница 2пз = О (пз) дает правильное представление об асимптотнческом поведении Глава 3. Рост Функций 95 функции, а граница 2п = О (из) его не обеспечивает.
Для обозначения того, что верхняя граница не является асимптотически точной оценкой функции, приме- няются о-обозначения. Приведем формальное определение множества о(д(п)) (произносится как "о малое от д от и"): 1 Г" (и): для любой положительной константы с существует о(д(п)) = '( пс > О, такое что О < 1' (и) < сд (и) для всех п > по Например: 2п = о (пз), но 2пз ф о (пз), Определения О-обозначений и о-обозначений похожи друг на друга. Основное отличие в том, что определение 1 (и) = О (д (и)) ограничивает функцию 1' (и) неравенством О < 1 (и) < сд (и) лишь для некоторой константы с > О, а определение Г" (и) = о(д(п)) ограничивает ее неравенством О < Г" (и) < сд(п) для всех констант с > О.
Интуитивно понятно, что в о-обозначениях функция г" (и) пренебрежимо мала по сравнению с функцией д (и), если и стремится к бесконечности, т.е. 1пп =О 1() а оо д(п) Некоторые авторы используют этот предел в качестве определения о-обозначений. Добавим, что определение, приведенное в этой книге, накладывает на безымянную функцию ограничение, согласно которому она должна быть асимптотически неотрицательной. (3. 1) пг-обозначения По аналогии, ш-обозначения соотносятся с П-обозначениями так же, как ообозначения с О-обозначениями. С помощью ы-обозначений указывается нижний предел, не являющийся асимптотически точной оценкой.
Один из возможных способов определения ы-обозначения следующий: 1'(и) 6 и(д(п)) тогда и только тогда, когда д(п) е о(Г(п)). 1 г" (и): для любой положительной константы с существует о(д(п)) = ) пс > О, такое что О < сд (и) < г (и) для всех п > по Например, пз/2 = ы (и), но пз(2 ф ы (пз). Соотношение г'(и) = ы (д (и)) подразумевает, что 11ш 4~ = оо, если этот предел существует.
Таким образом, и оо упн функция 1' (и) становится сколь угодно большой по сравнению с функцией д (и), если и стремится к бесконечности. Формально же м (д (п)) (произносится как "омега малое от д от п") определяется как множество 96 Часть й Основа Сравнение функций Асимптотические сравнения обладают некоторыми свойствами отношений обычных действительных чисел, показанными далее. Предполагается, что функции Г (и) и д (и) асимптотически положительны. Транзитивность Рефлексивность Симметричность т (и) = ст (д (и) ) справедливо тогда и только тогда, когда д (и) = 6 (~ (и) ) .
Перестановочная симметрия г" (и) = 0(д(п)) справедливо тогда и только тогда, когда д(п) = й(т (п)), ~ (и) = о (д (и) ) справедливо тогда и только тогда, когда д (п) = ьт (Г (п)) . Поскольку эти свойства выполняются для асимптотических обозначений, можно провести аналогию между асимптотическим сравнением двух функций т и д и сравнением двух действительных чисел а и 6: Говорят, что функция Г (и) асимпптоптически мепьше функции д (и), если г (и) = = о(д (и)), и асимпптоптпчески больше функции д(п), если ~ (и) = ы(д (и)). Однако одно нз свойств действительных чисел в асимптотических обозначениях не выполняется.
Из г (и) = ст (д (п) ) Из г" (и) = 0(д(и)) Из т (и) = й(д(и)) Из г (п) = о(д(п)) Из т (и) = ьт(д(п)) и д(п) = 0(Ь(п)) следует ~(п) = 8(Ь(п)). и д (и) = 0 (Ь (и) ) следует г' (и) = 0 (Ь (и) ) . и д (и) = Й (Ь (и) ) следует г (и) = Й (Ь (и) ) . и д(п) = о(Ь(п)) следует г" (п) = о(Ь(п)). и д (и) = ы (Ь (и) ) следует ~ (и) = ы (Ь (и) ) .
1 (п) = 6 (У (и) ), г" (и) = 0 (г" (и)), г (и) = Й (т (п)) . ,т (п) = 0 (д (и)) а < 6, г (п) = й (д (и)) — а > Ь, ~ (п) = 0 (д (и) ) — а = 6, т" (и) = о (д (и) ) — а < Ь, г" (и) = ьт (д (и)) = а > 6. Глава 3. Рост функций 97 Трихояюл~ия: для любых действительных чисел а и Ь должно выполняться только одно из соотношений а < Ь, а = Ь или а > Ь. Хотя любые два действительных числа можно однозначно сравнить, в отношении асимптотического сравнения функций это утверждение не является справедливым. Для двух функций Г (и) и д (и) может не выполняться ни отношение г" (п) = 0 (д (и)), ни г" (п) = й(д(п)).
Например, функции и и и1+""" нельзя асимптотически сравнивать, поскольку показатель степени в функции п|+""" колеблется между значениями О и 2 (принимая все значения в этом интервале). (и+ а) = 9 (и ) . (3.2) 3.1-3. Объясните, почему выражение "время работы алгоритма Л равно, как минимум, 0 (пз)" не имеет смысла. 3.1-4. Справедливы ли соотношения 2"+1 = 0 (2") и 2аи = О (2")? 3.1-5. Докажите теорему 3.1. 3.1-6. Докажите, что время работы алгоритма равно О (д (и)) тогда и только тогда, когда время работы алгоритма в наихудшем случае равно 0 (д (и)), а время работы алгоритма в наилучшем случае равно й (д (и)). 3.1-7.
Докажите, что множество о(д(п)) Пы(д(п)) пустое. 3.1-8. Наши обозначения можно обобщить для случая двух параметров и и т, которые могут возрастать до бесконечности с разной скоростью. Для данной функции д(п, т) выражение 0 (д (и, т)) обозначает множество функций, такое что ~ (п, т): существуют положительные константы с, по и то, такие что О < Т" (п, т) < сд (и, т) для всех п > по или т > то 0(д(п,т)) = Дайте аналогичные определения обозначений П (д (и, т) ) и О (д (и, т) ). Упражнения 3.1-1. Пусть г' (и) и д (и) — асимптотически неотрицательные функции. Докажите с помощью базового определения с1-обозначений, что гаах( Г" (п), д(п)) = Й (Г (п) + д (и)).
3.1-2. Покажите, что для любых действительных констант а и Ь, где Ь > О, справедливо соотношение Часть 1. Основы 98 В этом разделе рассматриваются некоторые стандартные математические функции и обозначения, а также исследуются взаимоотношения между ними. В нем также иллюстрируется применение асимптотических обозначений. Монотонность Функция / (и) является монотонно неубывающей (шопогошса11у шсгеаз1п8), если из неравенства т < и следует неравенство /(т) < /(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
