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