Асимптотически точная оценка функции роста

Если для функции T(n) найдутся константы c1 > 0 и c2 > 0 и такое число n0 > 0, что выполнится условие , то молвят что время выполнения метода (программки) асимптотически точно соответствует функции n2. Данный факт обозначается как , где n – длина входа метода.

Определение1. Вообщем, если и положительно определенные функции, то запись значит, что найдутся константы Асимптотически точная оценка функции роста c1 > 0 и c2 > 0 и такое n0 > 0, что для всех .

(Запись « » читается как «эф от эн есть тэта от же от эн»).

Если , то молвят, что является асимптотически четкой оценкой (asymptotically tight bound) для . По сути это отношение симметрично, если: , то .

Рис. 2. Иллюстрация к определению

Заметим, что есть обозначение факта некого Асимптотически точная оценка функции роста соотношения меж 2-мя функциями, потому, если установлено , а как следует и , то это совсем не значит, что .

Проиллюстрируем свойство симметрии функции . Можно показать, что . Согласно определению нужно указать положительные константы с1, с2 и число n0 так, чтоб неравенства

производились для всех . Разделим все части неравенства на n2:

.

Видно, что для выполнения Асимптотически точная оценка функции роста второго неравенства довольно положить c2 = 1/2. 1-ое будет выполнено, если (к примеру) n0 = 7 и c1=1/14.

Покажем, что По правде, пусть найдутся такие c2и n0, что для всех . Но тогда для всех , из чего следует что c2 не может является константой, потому что вырастает с повышением n, что Асимптотически точная оценка функции роста противоречит определению.

Упомянем принципиальный личный случай использования -обозначений: , который обозначает ограниченную функцию, отделённую от нуля некий положительной константой при довольно огромных значениях аргумента.

Асимптотические обозначения нередко употребляются снутри формул. К примеру, рекуррентное соотношение вида

значит, что время выполнения метода для входа длины n определяется временем выполнения для входной последовательности из (n–1) частей Асимптотически точная оценка функции роста и некой функции, про которую нам принципиально знать только, что она не меньше c1n и не больше c2n для неких положительных с1 и с2 и для всех довольно огромных n, которая по определению обозначается через . Другими словами, время работы программки при изменение входной длины возрастает пропорционально Асимптотически точная оценка функции роста n, а в методе этому члену в выражении соответствует кусок с асимптотической оценкой равной n.

Нередко асимптотические обозначения употребляются не полностью формально, хотя их подразумеваемый смысл обычно ясен из контекста.

Обычный пример неформального использования асимптотических обозначений – цепочка равенств вида . 2-ое из этих равенств понимается при всем этом так Асимптотически точная оценка функции роста: какова бы ни была функция в левой части, сумма есть .

Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены наименьшего порядка, которые при огромных n становятся малыми по сопоставлению с главным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может воздействовать лишь на выбор констант Асимптотически точная оценка функции роста с1и с2). К примеру, разглядим квадратичную функцию , где a, b, c – некие константы и a > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим что Чтоб убедиться в этом формально, можно положить с1= a/4, c2 = 7a/4и . Вообщем, для хоть какого полинома p(n) степени d с положительным старшим Асимптотически точная оценка функции роста коэффициентом имеем .

1.3.2 - и - обозначения

Вообщем, запись содержит в себе две оценки: верхнюю и нижнюю. Их можно поделить:

Определение 2. Пусть имеются функции и , которые принимают неотрицательные значения для довольно огромных значений аргумента. Молвят, что , если найдётся такая константа c > 0 и такое число n0, что для всех (рис. 3а).

Определение3. Молвят, что , если найдётся Асимптотически точная оценка функции роста такая константа c > 0 и такое число n0, что для всех (рис. 3б). Эти записи читаются так: «эф от эн есть о огромное от же от эн», «эф от эн есть омега большая от же от эн».

Аксиома1.Для всех 2-ух функций и свойство выполнено и тогда только тогда, когда Асимптотически точная оценка функции роста и .

Замечание: Для всех 2-ух функций и свойство и равносильны.

(а) (б)
Рис. 3. Верхняя (а) и нижняя (б) асимптотические оценки функции

Асимптотические обозначения могут употребляются снутри формул. К примеру, мы можем написать выражение

имея в виду сумму h(1) + h(2) + … + h(n), где h(×) – некая функция, для которой h Асимптотически точная оценка функции роста(i) = O(i). Можно показать, что сама эта сумма как функция от n есть O(n2).

1.3.3 и обозначения

Запись значит, что с ростом n отношение остаётся ограниченным. Если к тому же

,

то мы пишем (читается «эф от эн есть о маленькое от же от эн»). Формально говоря, , если для всякого положительного найдётся Асимптотически точная оценка функции роста такое n0, что при всех . Тем запись подразумевает, что и неотрицательны для довольно огромных n.

Пример: но

Аналогичным образом вводится обозначение: молвят, что есть («эф от эн есть омега малая от же от эн»), если для всякого положительного e найдется такое n0, что при всех , при этом

.

Разумеется, равносильно Асимптотически точная оценка функции роста

Пример: , но

Таким макаром, может существовать три главных варианта (существует и 4-ый случай, когда предела не существует, но он встречается достаточно изредка в реальной практике анализа алгоритмов):

Но на практике серьезными определениями пользуются изредка. Существует более удачный способ выполнения этой оценки, основанный на массивном математическом аппарате, специально предназначенного для вычисления Асимптотически точная оценка функции роста пределов дела 2-ух рассматриваемых функций, а именно правилом Лопиталя (L'Hopital):

и формулой Стирлинга (Stirling) для довольно огромных n:

.

Пример 1. Сравните порядки роста функций f(n)=n(n – 1)/2 и g(n)=n2.

Решение: так как

предел равен положительной константе, обе функции имеют однообразный порядок роста, что записывается как .

Пример 2. Сравните порядки Асимптотически точная оценка функции роста роста функций и .

Решение:

.

Так как предел равен нулю, функция имеет наименьший порядок роста, чем . Другими словами .

Пример 3. Сравните порядки роста функций и .

Решение: воспользовавшись формулой Стерлинга, получим:

Как следует, хотя функция вырастает очень стремительно, функция вырастает еще резвее, что записывается как . Обратим внимание, что при использовании этой Асимптотически точная оценка функции роста формы записи, в отличие от варианта использования пределов, не можем сделать конкретный вывод о том, что порядок роста функции выше, чем функции , а не, скажем, равен ей, потому употребляется «большая» омега.


astahov-gubernatori-dolzhni-otvechat-za-usinovlenie-detej-inostrancami.html
astahov-schitaet-nepriemlemimi-dlya-rf-zapadnie-tehnologii-yuvenalnoj-yusticii.html
astana-innovations-v-pervij-stolichnij-venchurnij-startap-fond-smozhet-obratitsya-lyuboj-startaper.html