Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 19
Текст из файла (страница 19)
Теорема 3.1. Для ~юбых двух функций Г"(п) и д(п) соотношение Г"(п) = 0(д(п)) выполняется тогда и только тогда, когда ~(п) = 0(д(п)) и У(и) = й(д(п)) О В качестве примера применения этой теоремы отметим, что из соотношения апз + Ьп + с = 9 (пз) для произвольных юнстант а, Ь и с, где а > О, непосред- Глава 3. Рост функций 93 отвеина следует, что апз + Ьп + с = О (пз) и апз + Ьп + с = й (пз).
На практике терема 3.1 применяется не для получения асимптотических верхней и нижней границ, как это сделано выше, а наоборот — для определения асимптотически точной оценки с помощью асимптотических верхней и нижней границ. Поскольку й-обозначения используются для определения нижней границы времени работы алгоритма в наилучшем случае, они также дают нижнюю границу времени работы алгоритма для произвольных входных данных. Итак, время работы алгоритма сортировки вставкой находится в пределах между й (и) и О (пз), т.е. между линейной и квадратичной функциями от и.
Более того, эти границы охватывают асимптотику настолько плотно, насколько это возможно: например, нижняя оценка для времени работы алгоритма сортировки вставкой не может быть равной й (пз), потому что существуют входные данные, для которых эта сортировка выполняется за время О (и) (когда входные элементы уже отсортированы), что не противоречит утверждению о том, что время работы алгоритма сортировки вставкой в наихудшем случае равно Й (пз), поскольку существуют входные данные, для которых этот алгоритм работает в течение времени й (пэ). Когда говорят, что время рабансес (без каких-либо уточнений) алгоритма равно Й (д (и) ), при этом подразумевается, что независимо онс нюго, какие входные данные выбраны для данного размера и, при достаточно больших п время работы алгоритма представляет собой как минимум константу, умноженную на д (и).
Асимптотические обозначения в уравнениях и неравенствах Мы уже видели, как асимптотические обозначения используются в математических формулах. Например, при введении О-обозначения мы писали "и = = О (пэ)". Можно также написать 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пз + д(п) = 6(п). Заметим, что такая интерпретация подразумевает выполнение соотношения 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 Трихояюл~ия: для любых действительных чисел а и Ь должно выполняться только одно из соотношений а < Ь, а = Ь или а > Ь. Хотя любые два действительных числа можно однозначно сравнить, в отношении асимптотического сравнения функций это утверждение не является справедливым.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
