Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 16
Текст из файла (страница 16)
Например, в главе 2 мы имели возможность убедиться в том, что если входные элементы уже отсортированы, то время работы алгоритма сортировки вставкой составляет 0(п). Технически неверно говорить, что время, необходимое для сортировки по методу вставок, равно 0(пз), так как для данного п фактическое время работы алгоритма изменяется в зависимости от конкретных входных данных. Когда говорится, что "время работы равно 0(пз)", то подразумевается, что существует функция г"(и), принадлежащая О(пз), такая, что при любых входных данных размером и время решения задачи с этими входными данными ограничено сверху значением функции г(п).
В конечном счете подразумевается, что в наихудшем случае время работы равно 0(пз). й-обозначения Подобно тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в П-обозначениях дается ее асимятотическая нижняя граница. Для данной функции д(п) выражение П(д(п)) (произносится как "омега большое от д от и'* или просто как "омега от д от и") обозначает множество функций й(д(п)) = (г (п); существуют положительные константы с и по, такие, что 0 ( сд(п) <,Г"(п) для всех и > по) . Глава 3, Раат функций Интуитивное представление об Й-обозначениях дает рис.
3.1, (в). Для всех п, лежащих справа от по, значения функции Т(п) больше или равны значениям сд(п). Пользуясь введенными определениями асимптотических обозначений, легко доказать сформулированную ниже теорему (см. упр. 3.1.5). Теорема 3.л Для любых двух функций Дп) и д(п) мы имеем Д(п) = су(д(п)) тогда и только тогда, когда Дп) = 0(д(п)) и Т(п) = Й(д(п)). В качестве примера применения этой теоремы отметим, что из соотношения аиз + Ьи + с = сз(пз) для произвольных констант а, Ь и с, где а > О, непосредственно следует, что аи~ + Ьп + с = 0(п~) и аи + Ьи + с = Й(пз). На практике теорема 3.1 применяется не для получения асимптотических верхней и нижней границ, как это сделано выше, а наоборот — для определения асимптотически точной оценки с помощью асимптотических верхней и нижней границ.
Когда мы говорим, что время работы (без указания модификатора) алгоритма равно Й(д(п)), мы имеем в виду, что независимо от того, какие конкретно входные данные размером п выбраны для каждого значения п, время работы для этих входных данных будет для достаточно больших и как минимум константой, умноженной на д(п). Или, что то же самое, мы даем нижнюю границу времени работы алгоритма в наилучшем случае. Например, в наилучшем случае время работы сортировки вставкой составляет Й(п), откуда следует, что время работы сортировки вставкой представляет собой Й(п). Таким образом, время работы алгоритма сортировки вставкой принадлежит как Й(п), так и О(пз), поскольку оно располагается между линейной и квадратичной функциями от п. Более того, эти границы охватывают асимптотику настолько плотно, насколько это возможно.
Например, нижняя оценка лля времени работы алгоритма сортировки вставкой не может быть равной Й(пз), потому что существуют входные данные, для которых эта сортировка выполняется за время 6(и) (когда входные элементы уже отсортированы). Это не противоречит утверждению о том, что время работы алгоритма сортировки вставкой в наихудшем случае равно Й(п~), поскольку существуют входные данные, для которых этот алгоритм работает в течение времени Й(пз). Асимптотические обозначения в уравнениях и неравенствах Мы уже видели, как асимптотические обозначения используются в математических формулах.
Например, при введении 0-обозначения мы писали '*п = 0(из)". Можно также записать "2из + Зп + 1 = 2из + 9(п)". Как же интерпретируются подобные формулы? Если в правой части уравнения (или неравенства) находится только асимптотическое обозначение (не являющееся частью большей формулы), как в случае уравнения п = О(п ), то знак равенства используется для указания принадлежности множеству: и е 0(пз).
Однако если асимптотические обозначения встречаются в формуле в другой ситуации, они рассматриваются как подставляемые вместо некоторой неизвестной функции, имя которой не имеет значения. Напри- Часть 1 Основы мер, формула 2пз+Зп+1 = 2пз+Э(п) означает, что 2пз+Зп+1 = 2пз+1(п), где у" (и) — некоторая функция из множества Н(п). В данном случае г'(и) = Зп + 1, и эта функция действительно принадлежит множеству Й(п). Подобное использование асимптотическнх обозначений позволяет избежать несущественных деталей и неразберихи в уравнениях. Например, в главе 2 время работы сортировки слиянием в наихудшем случае было выражено в виде рекуррентного уравнения Т(п) = 2Т(п/2) + 9(п) . Если нас интересует только асимптотическое поведение Т(п), то нет смысла точно выписывать все слагаемые низших порядков; подразумевается, что все они включены в безымянную функцию, обозначенную как 0(п).
Предполагается, что таких функций в выражении столько, сколько раз в нем встречаются асимптотические обозначения. Например, в выражении ,'>,". 0(г) имеется только одна функция без имени (аргументом которой является г). Таким образом, это выражение — не то же самое, что и 0(1) + 0(2) + .. + 0(п), выражение, которое действительно не имеет однозначной интерпретации. В некоторых случаях асимптотические обозначения появляются в левой части уравнения, как, например, в 2пз + Еэ(п) = тЗ(пз) . Подобные уравнения интерпретируются в соответствии со следующим правилом: при любам выборе безымянных функций, подставляемых вместо асииптотических обозначений в левую часть уравнения, можно выбрать и подставить в правую часть такие безымянные функции, что уравнение будет правильным.
Таким образом, наш пример означает, что для любой функции 1"(и) Е 6(п) существует некоторая функция д(п) Е 6(пэ), такая, что 2п~ + 1(п) = д(п) для всех п. Другими словами, правая часть уравнения предоставляет меньший уровень детализации, чем левая. Такие соотношения могут быть объединены в цепочку, как в 2пз+ Зп+ 1 = 2пз + 0(п) =9(п ) .
При этом в соответствии со сформулированными выше правилами можно интерпретировать каждое уравнение отдельно. Согласно первому уравнению существует некоторая функция у(п) Е чз(п), такая, что для всех п выполняется соотношение 2пз + Зп + 1 = 2пз + 1(п). Второе уравнение гласит, что для любой функции д(п) Е 0(п) (такой, как только что упоминавшаяся 1(п)) существует некоторая функция Й(п) Е чз(п ), такая, что для всех и выполняется соотношение 2пз + д(п) = Ь(п). Заметим, что такая интерпретация подразумевает выполнение соотношения 2пз + Зп + 1 = 9(пз), которое согласуется с нашими интуитивными представлениями о цепочке уравнений.
75 Глава 3. Рост функций о-обозначения Асимптотическая верхняя граница, предоставляемая О-обозначениями, может описывать асимптотическое поведение функции с разной точностью, Граница 2пз = О(пз) дает правильное представление об асимцтотичесюм поведении функции, а граница 2п = 0(пз) — нет. Для указания того, что верхняя граница не является асимптотнчески точной оценкой функции, применяются о-обозначения. Приведем формальное определение множества о(д(п)) (произносится как "о малое ог д от и"): ( („)) (лс(п); длЯ любои положительнои константы с > О существует константа по > О, такая, что О < У(п) < сд(п) для всех и > по) . Например, 2п = о(пз),но 2пз ,-Е о(пз), Определения 0-обозначений и о-обозначений похожи между собой.
Основное отличие в том, что определение 5(п) = 0(д(п)) ограничивает функцию 5(п) неравенством О < 5"(п) < сд(п) лишь для некоторой константы с > О, а определение 5"(п) = о(д(п)) ограничивает ее неравенством О < 5(п) < сд(п) для всех констант с > О. Интуитивно понятно, что в о-обозначениях функция 5"(п) пренебрежимо мала по сравнению с функцией д(п) при п, стремящемся к бесконечности, т.е. 1пп — = О .
Пп) (3.1) и-+ос д(П) Некоторые авторы используют этот предел в качестве определения о-обозначений. Добавим, что определение, данное в этой книге, накладывает на безымянную функцию ограничение, согласно которому она должна быть асимптотически неотрицательной. ы-обозначения По аналогии ы-обозначения соотносятся с й-обозначениями точно так, как о-обозначения с О-обозначениями. С помощью ы-обозначений указывается нижний предел, не являющийся асимптотически точной оценкой. Один из возможных способов определения ы-обозначения следующий: 5 (и) б ы(д(п)) тогда и толью тогда, югда д(п) б о(5 (и)) . Формально же ы(д(п)) (произноснтся как "омега малое от д от и") определяется как множество ы(д(п)) = (У(п): для любой положительной юнстанты с > О существует константа по > О, такая, что О < сд(п) < 5(п) для всех и > по) .
часть я Основы Например, пз/2 = ш(п), но пз/2 ~ ш(п ). Из соотношения Дп) = ш(д(п)) вытекает, что 1пп — = оо, ~(п) и†>со д(п) если этот предел существует. Таким образом, функция г'(п) становится сюль угодно большой по сравнению с функцией д(п) прн п, стремящемся к бесюнечности. Сравнение функций Асимптотические сравнения обладают многими свойствами отношений обычных действительных чисел, показанными далее, Здесь предполагается, что функции Дп) и д(п) асимптотически положительны.
Транзитнвность Рефлексивность Симметрия г" (п) = 9(д(п)) тогда и только тогда, когда д(п) = 6(Г" (п)) Перестановочная симметрия 1(п) = О(д(п)) тогда итолько тогда,когда д(п) = й(1'(п)) г" (п) = о(д(п)) тогда и толью тогда, югда д(п) = ы(Дп)) Из-за выполнения указанных свойств для асимптотических обозначений можно провести аналогию между асимптотическим сравнением двух функций 1 и д Из г"(п) = Из г"(п) = Из г'(п) = Из У(п) = Из г"(п) = 9(д(п)) и д(п) = 9(Ь(п)) 0(д(п)) и д(п) = О(Ь(п)) Й(д(п)) и д(п) = Й(Ь(п)) о(д(п)) и д(п) = о(Ь(п)) ш(д(п)) и д(п) = ш(Ь(п)) следует следует следует следует следует 1'(п) = ~(Яп)) 1(п) = ОЩп)) г" (п) = й(1'(п)) 1(п) = 6(Ь(п)) ~(п) = 0(Ь(п)) Дп) = й(Ь(п)) ,1(п) = о(Ь(п)) г(п) = ы(Ь(п)) Глава 3. Рост функций 77 и сравнением двух действительных чисел а и Ь. 1 (п) = 0(д(п) ) 1 (п) = Й(д(п) ) 1(п) = 6(д(п)) 1(п) = о(д(п)) Г(п) = ы(д(п)) аналогично а < 6 аналогично а > 6 а =Ь аналогично аналогично аналогично а<6 а>Ь Говорят, что функция 1(п) асамлтотически меньше функции д(п), если 1(п) = о(д(п)), н асаматотическа баловне функции д(п), если 1(п) = ю(д(п)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
