Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Поскольку ез(д(п)) представляет собой множество, можно записать "у (п) Е (Э(д(п))", чтобы указать тот факт, что )'(п) является членом 6(д(п)). Вместо этого мы обычно будем использовать эквивалентную запись "у(п) = гз(д(п))". Такое толкование знака равенства для обозначения принадлежности множеству поначалу может сбить с толку, однако далее мы убедимся, что у этой записи есть свои преимущества. (л) л) л) л) л) л л л лл лл лр да МЕ(цл)) ЯлЬО(Г(л)) ял) (дя(л)) (л) (б) (л) Рнс. ЗЛ. Графические примеры Вч О- и Й-обозначений. Н каждой части значение па валяется минимально возможным; подходит глюке любое большее значение.

(а) ег-обозначение ограничивает фующию константными множителями. Мы записываем Г(п) = Э(д(п)), если существуют положительные константы па, с( и сз, такие, что в точке пс и справа от нее значение Г" (и) всегда лежит между с(д(п) и сзд(п) вюючительно. (б) О-обозначение дает верхюою оценку функции с точностью до посгоюшого множителя.

Мы записываем Дп) = О(д(п)), если существуют палозопельные юнстанты па н с, такие, что в точке па и справа ат нее значение Г'(и) всегда лежит не выше сд(п), (в) Й-обозначение дает нюкнюю оценку функции с точностью до постоянного множителя. Мы записываем г" (и) = Й(д(п)), если существуют пололппельиые юнсгангы па и с, такие, что а тачке ца и справа от нее значение Дп) всегда лежит не ниже сд(г().

На рис. 3.!, (а) показано интуитивное изображение функций )'(п) и д(п), таких, что )(и) = ез(д(п)). Для всех значений п, лежащих справа от по, функция У (и) больше или равна функции с)д (и), но не превосходит функцию сад (и). Другими словами, для всех и ) по функция ) (и) равна функции д (п) с точностью до В глория мяанеста дваегачие следует читать яая "такие, чзо" яля "Лля впарил выпалнлегея уславиет 70 Часть 1 Основы постоянного множителя. Говорят, что функция д(п) является асимлтотически точной оценкой функции / (п). Согласно определению множества 9 (д(п)) необходимо, чтобы каждый элемент /(п) е Й(д(п)) этого множества был асимлтотически неотрицателен. Это означает, что при достаточно больших п функция /(п) является неотрицательной.

(Асимлтотически лоложительной называется такая функция, которая является положительной при любых достаточно больших п.) Следовательно, функция д (п) должна быть асимптотически неотрицательной, потому что в противном случае множество й(д(п)) окажется пустым. Поэтому будем считать, что все функции, используемые в гэ-обозначениях, асимптотически неотрицательные. Это предположение справедливо и для других асимптотических обозначений, определенных в данной главе.

В главе 2 ев-обозначения вводятся неформально. При этом отбрасываются слагаемые низшего порядка и игнорируется коэффициент при старшем слагаемом. Подтвердим интуитивные представления, рассмотрев небольшой пример, в котором с помощью формального определения показано, что -пэ — Зп = 9(пз). Для этого необходимо определить, чему равны положительные константы сы с2 и по, такие, что с1п < -п — Зп < сзп 2 1 2 2 2 для всех п > по.

Деление на п2 дает 1 3 С1 « — — — С2 2 Можно сделать правое неравенство выполняющимся для любого значения п > 1, выбирая любую константу с2 > 1/2. Аналогично можно сделать выполняющимся для любого значения п > 7 левое неравенство, если выбрать произвольную константу с1 < 1/14. Таким образом, выбирая с1 = 1/14, с2 = 1/2 и по = 7, можно убедиться, что 2пз — Зп = 9(пз).

Конечно, имеются и другие варианты выбора констант, но главное заключается в том, что такой выбор существует. Заметим, что эти константы зависят от функции 1п — Зп; другой функции, принадлежащей 9(п2), скорее всего, потребуются другие константы. Можно воспользоваться формальным определением для того, чтобы убедиться, что 6пз ф 9(пз).

Пойдем от противного, предположив, что существуют константы с2 и по„такие, что бп < сзп для всех п > по. Но тогда деление на пз дает п < сэ/6, а это неравенство не может выполняться при произвольно больших п, поскольку с2 является константой. Интуитивно понятно, что при асимптотически точной оценке асимптотически положительных функций, слагаемыми низших порядков в них можно пренебречь, поскольку при больших п они становятся несущественными.

При больших п даже небольшой доли слагаемого самого высокого порядка достаточно для того, чтобы превзойти слагаемые низших порядков, Таким образом, для выполнения неравенств, фигурирующих в определении й-обозначений, достаточно в качестве с1 выбрать значение, которое несколько меньше коэффициента при самом старшем слагаемом, а в качестве сз — значение, которое несколько больше этого ко- у! Глася 3. Рост функций зффициеита. Поэтому коэффициент при старшем слагаемом можно не учитывать, так как он лишь изменяет указанные константы. В качестве примера рассмотрим произвольную квадратичную функцию /(и) = апз + Ьп + с, где а, Ь и с — константы, причем а > О. Отбросив слагаемые низших порядков и проигнорировав константу, получим /(и) = ту(п ).

Чтобы показать то же самое формально, выберем константы су = а/4, сз = 7а/4 н пб = 2 шах(~6(/а, „/(с) /а). Читатель может сам убедиться в том, что неравенство О < супу < апз + 6п + с < сзпз выполняется для всех и > по. В общем случае для любого полинома р(п) = 2',з о а,п', где а, представляют собой жунг станты и ав > О, мы имеем р(п) = цу(п~) (см. задачу 3.1). Поскольку любая константа — это полинам нулевой степени, постоянную функцию можно выразить как ту(пс) или Э (1). Однако последнее обозначение не совсем точное, поскольку непонятно, по отношению к какой переменной исследуется асимптотиказ. Мы часто будем употреблять запись ез (1) для обозначения либо цонстанты, либо постоянной функции по отношению к некоторой переменной.

0-обозначения В 9-обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимплеотическую верхнюю границу, используются 0-обозначения. Для данной функции д(гь) обозначение 0 (д (и)) (произносится как "о большое от д от п" или просто "о от д от и") означает множество функций 0(д(п)) = (/(и): существуют положительные константы с и по, такие, что О < /(и) < сд(п) для всех и > по) . 0-обозначения примеюпотся, когда нужно указать верхнюю границу функции с точностью до постоянного множителя. Интуитивное представление об О-обозначениях позволяет получить рис. 3.1, (б). Для всех значений и, лежащих справа от по, значение функции / (и) не превышает значения функции сд (п).

Чтобы указать, что функция / (и) принадлежит множеству 0 (д (и)), используется зались /(и) = 0(д(п)). Обратите внимание, что из /(и) = цу(д(п)) следует /(и) = 0(д(п)), поскольку гу-обозначения более сильные, чем О-обозначения. В обозначениях теории множеств гу(д(п)) С О(д(п)). Таким образом, доказательство того, что функция апз + 6п + с, где а > О, принадлежит множеству 6(пз), одновременно доказывает, что любая такая квадратичная функция является элементом множества 0(пз). Может показаться удивительным то, что любая линейная функция оп+ Ь при а > О также принадлежит множеству 0(п ).

В этом легко убедиться, выбрав с = а+ (Ь| и по = шах(1, — Ь/а). зна самом деле проблема заключается в гом, что в пашня обычньш обозначенная фупкплй не делвстса разлпчла между фупкцлямн и обычными велнчпнамп, В Л-лсчпслснпп четко уквзывмогса параметры функций; функцию ог пз можно обозначить как Лп.оз плп даже как Лгжз. Однмго если принять более сгрогпе обозначенпа, го аягебрапческле преобразоаанпа могуг усложплгься, поэтому мы преппочлн нестрогле обозпаченля. Часть 2 Основы Некоторым читателям, уже знакомым с О-обозначениями, может показаться странным, например, соотношение и = О(пз).

В литературе О-обозначения иногда неформально используются для описания асимптотической точной оценки, т.е. так, как мы определили 9-обозначения. Однако в данной книге, когда мы пишем )(и) = О(д(п)), подразумевается, что произведение некоторой константы на функцию д(п) является асимптотическим верхним пределом функции ~(п), При этом не играет роли, насколько близко функция г" (п) находится к этой верхней границе. В литературе, посвященной алгоритмам, стало стандартом различать асимптотически точную оценку и верхнюю асимптотическую границу. Чтобы записать время работы алгоритма в О-обозначениях, зачастую достаточно просто изучить его общую структуру.

Например, наличие двойного вложенного цикла в структуре алгоритма сортировки вставкой, представленного в главе 2, свидетельствует о том, что верхний предел времени работы в наихудшем случае выражается как 0(пз); стоимость каждой итерации во внутреннем цикле ограничена сверху константой О(1), индексы з и у — числом и, а внутренний цикл выполняется самое большее один раз для каждой из пз пар значений з и з. Поскольку 0-обозначения описывают верхнюю границу, когда мы используем их для ограничения времени работы алгоритма в наихудшем случае, мы получаем верхнюю границу этой величины для любых входных данных — то самое всеобъемлющее утверждение, о котором мы говорили ранее. Таким образом, граница 0(пз) для времени работы алгоритма в наихудшем случае применима для времени решения задачи с любыми входными данными, чего нельзя сказать о 9- обозначениях. Например, оценка 9(пз) для времени сортировки вставкой в наихудшем случае неприменима для любых входных данных.

Характеристики

Список файлов книги