Асимптотические обозначения

Термины   27 мая 2012  Автор статьи:  
geekbrains.ru/

Асимптотические обозначения позволяют оценить время время работы алгоритма, являются наглядной характеристикой эффективности алгоритма, а также позволяет сравнивать производительность различных алгоритмов. Например, для сортировок если количество сортируемых элементов n становится достаточно большим, производительность алгоритма сортировки по методу слияний, время работы которого в наихудшем случае возрастает как O(n\cdot\log{n}), становится выше производительности алгоритма сортировки вставкой, время работы которого в наихудшем случае возрастает как в O(n^2). Несмотря на то, что в некоторых случаях можно определить точное время работы алгоритма, обычно не стоит выполнять оценку с большой точностью. Для достаточно больших входных данных постоянные множители и слагаемые низшего порядка, фигурирующие в выражении для точного времени работы алгоритма, подавляются различными эффектами.

\mathbf{\Theta-\cyr Oboznacheniya(poryadok rosta)}
Для некоторой функции g(n) запись \theta(g(n)) обозначает множество функций:
\theta(g(n))= \{f(n)|\: \exist c_1>0,\: c_2>0,\: n_0>0 \: : \: \forall n\ge n_0 \:\:\:\:\: 0\le c_1g(n)\le f(n)\le c_2g(n)\}
Функция g(n) принадлежит множеству \theta(g(n)), если существуют положительные константы c_1 и c_2, позволяющие заключить эту функцию в рамки между функциями c_1(n) и c_2f(n) для достаточно больших n. Поскольку \theta(g(n))— это множество, то можно написать f(n)\in\theta(g(n)). Это означает, что функция f(n) принадлежит множеству \theta(g(n)) (другими словами, является его элементом). Обычно используется эквивалентная запись f(n)=\theta(g(n)).
Для всех значений п, лежащих справа от n_0, функция f(n) больше или равна функции c_1g(n), но не превосходит функцию c_2g(n).Другими словами, для всех n\ge n_0функция f(n) равна функции g(n) с точностью до постоянного множителя. Говорят, что функция g(n) является асимптотически точной оценкой функции f(n).
Согласно определению множества в \theta(g(n)), необходимо, чтобы каждый элемент f(n) \in \theta(g(n)) этого множества был асимптотически неотрицателен. Это означает, что при достаточно больших n функция f(n) является неотрицательной. (Асимптотически положительной называется такая функция, которая является положительной при любых достаточно больших п). Следовательно, функция g(n) должна быть асимптотически неотрицательной, потому что в противном случае множество в (g(n)) окажется пустым. Поэтому будем считать, что все функции, используемые в \theta-обозначениях, асимптотически неотрицательные. Это также справедливо для других асимптотических обозначений.
Интуитивно понятно, что при асимптотически точной оценке асимптотически положительных функций, слагаемыми низших порядков в них можно пренебречь, поскольку при больших n они становятся несущественными. Даже небольшой доли слагаемого самого высокого порядка достаточно для того, чтобы превзойти слагаемые низших порядков. Таким образом, для выполнения неравенств, фигурирующих в определении \theta-обозначений, достаточно в качестве c_1 выбрать значение, которое несколько меньше коэффициента при самом старшем слагаемом, а в качестве c_2 — значение, которое несколько больше этого коэффициента. Поэтому коэффициент при старшем слагаемом можно не учитывать, так как он лишь изменяет указанные константы.
Поскольку любая константа — это полином нулевой степени, то постоянную функцию можно выразить как \theta(n^0) или \theta(1). Однако последнее обозначение не совсем точное, поскольку непонятно, по отношению к какой переменной исследуется асимптотика. Мы часто будем употреблять \theta(1) для обозначения либо константы, либо постоянной функции от какой-нибудь переменной.

\mathbf{O-\cyr Oboznacheniya(verxnyaya granitsa)}

В \theta-обозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются О-обозначения. Для данной функцииg(n) обозначение O(g(n)) (произносится «о большое от g от n» или просто «о от g от n») означает множество функций:
O(g(n))= \{f(n)|\: \exist c>0,\: n_0\ge0 \: : \: \forall n> n_0 \:\:\:\:\: 0\le f(n)\le cg(n)\}
О-обозначения применяются, когда нужно указать верхнюю границу функции с точностью до постоянного множителя. Для всех n, лежащих справа от по, значение функции f(n) не превышает значения функции cg(n). Чтобы указать, что функция f(n) принадлежит множеству О (g(n)), пишут f (n) = О (g(n)). Обратите внимание, что из f(n) = \theta(g(n)) следует f(n) = О (g(n)), поскольку \theta-обозначения более сильные, чем О-обозначения. В обозначениях теории множеств O(g(n)) \in \theta(g(n)). Таким образом, доказательство того, что функция an^2+bn+c, где а > О, принадлежит множеству \theta(n^2), одновременно доказывает, что множеству О (п2) принадлежит любая такая квадратичная функция. Может показаться удивительным то, что любая линейная функция an + b при а > 0 также принадлежит множеству O(n^2), что легко проверить, выбрав с = a + |b| и n_0 = max(1,-b/a).
Некоторым уже знакомым с О-обозначениями, может показаться странным, например, такое соотношение n = O(n^2). В литературе О-обозначения иногда неформально используются для описания асимптотической точной оценки, т.е. так, как мы определили \theta-обозначения. Однако когда мы пишем f(n) = О (g (n)), то при этом подразумевается, что произведение некоторой константы на функцию g(n) является асимптотическим верхним пределом функции f(n). При этом не играет роли, насколько близко функция f(n)находится к этой верхней границе. В литературе, посвященной алгоритмам, стало стандартом различать асимптотически точную оценку и верхнюю асимптотическую границу.
Чтобы записать время работы алгоритма в О-обозначениях, нередко достаточно просто изучить его общую структуру.Например, наличие двойного вложенного цикла в структуре алгоритма сортировки по методу вставок, свидетельствует о том, что верхний предел времени работы в наихудшем случае выражается как O(n^2): «стоимость» каждой итерации во внутреннем цикле ограничена сверху константой O(1), индексы i и j — числом n, а внутренний цикл выполняется самое большее один раз для каждой из n^2 пар значений i и j.
Поскольку О-обозначения описывают верхнюю границу, то в ходе их использования для ограничения времени работы алгоритма в наихудшем случае мы получаем верхнюю границу этой величины для любых входных данных. Таким образом, граница O(n^2) для времени работы алгоритма в наихудшем случае применима для времени решения задачи с любыми входными данными, чего нельзя сказать о \theta-обозначениях. Например, оценка в \theta(n^2) для времени сортировки
вставкой в наихудшем случае неприменима для произвольных входных данных.
Если подходить формально, то неправильно говорить, что время, необходимое для сортировки по методу вставок, равняется O(n^2), так как для данного n фактическое время работы алгоритма изменяется в зависимости от конкретных входных данных. Когда говорят, что «время работы равно O(n^2)«, то подразумевается, что существует функция f(n), принадлежащая O(n^2) и такая, что при любом вводе размера n, время решения задачи с данным вводом ограничено сверху значением функции f(n). Это равнозначно тому, что в наихудшем случае время работы равно O(n^2).

\mathbf{\Omega-\cyr Oboznacheniya(nizhnyaya granitsa)}

Аналогично тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в \Omega-обозначениях дается ее асимптотическая нижняя граница.Для данной функции g(n) выражение \Omega(g(n)) (произносится «омега большое от g от n» или просто «омега от g от n») обозначает множество функций, таких что
\Omega(g(n))= \{f(n)|\: \exist c>0,\: n_0>0 \: : \: \forall n\ge n_0 \:\:\:\:\: 0\le cg(n)\le f(n)\}
Для всех n, лежащих справа от n_0, значения функции f(n) больше или равны значениям сg(n). Поскольку \Omega-обозначения используются для определения нижней границы времени работы алгоритма в наилучшем случае, они также дают нижнюю границу времени работы алгоритма для произвольных входных данных.

\mathbf{o-\cyr Oboznacheniya}

Верхняя асимптотическая граница, предоставляемая О-обозначениями, может описывать асимптотическое поведение функции с разной точностью. Граница 2*n^2 = O(n^2) дает правильное представление об асимптотическом поведении функции, а граница 2*n = O(n^2) его не обеспечивает. Для обозначения того, что верхняя граница не является асимптотически точной оценкой функции, применяются о-обозначения. Приведем формальное определение множества о(g(n)) (произносится как «о малое от g от n»):
o(g(n))= \{f(n)|\: \forall c>0,\:\:\: \exist n_0>0 \: : \: \forall n\ge n_0 \:\:\:\:\: 0\le f(n)< cg(n)\}

Например: 2n = o(n^2), но 2n^2 \ne o(n^2). Определения О-обозначений и о-обозначений похожи друг на друга. Основное отличие в том, что определение f(n) = О(g(n)) ограничивает функцию f(n) неравенством 0\le f(n)\le cg(n) лишь для некоторой константы с > 0, а определение f(n) = о(g(n)) ограничивает ее неравенством 0\le f(n)< cg(n) для всех констант с > 0. Интуитивно понятно, что в о-обозначениях функция f(n) пренебрежимо мала по сравнению с функцией д(п), если п стремится к бесконечности, т.е:
\lim_{n\to \infty}{\frac{f(n)}{g(n)}} = 0
Некоторые авторы используют этот предел в качестве определения о-обозначений.

\mathbf{\omega-\cyr Oboznacheniya}

По аналогии, \omega-обозначения соотносятся с \Omega-обозначениями так же, как о-обозначения с О-обозначениями. С помощью \omega-обозначений указывается нижний предел, не являющийся асимптотически точной оценкой. Один из возможных способов определения \omega-обозначения следующий:
f(n)\in\omega(g(n)) тогда и только тогда, когда g(n)\in o(f(n)).
Формально же \omega(g(n)) (произносится как «омега малое от д от п») определяется как множество:
\omega(g(n))= \{f(n)|\: \forall c>0,\:\:\:\exist n_0>0 \: : \: \forall n\ge n_0 \:\:\:\:\: 0\le cg(n)< f(n)\}
Например,n^2/2 = \omega(n), но n^2/2 \ne \omega(n^2).
Соотношение f(n) = \omega(g(n)) подразумевает, что \lim_{n\to \infty}{\frac{f(n)}{g(n)}} = \infty , если этот предел существует. Таким образом, функция f(n) становится сколь угодно большой по сравнению с функцией g(n),
если n стремится к бесконечности.

Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов. Это означает, что нас интересует только то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности. Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких.

Научиться программировать

  • на Delphi

  • на Java

  • на C++

geekbrains.ru/
geekbrains.ru/