Основы анализа эффиктивности алгоритмов

Оценка размера входных данных. Единицы измерения времени выполнения алгоритма. Порядок роста. Основные классы эффективности. Соотношения, используемые при анализе алгоритмов.

15.Асимпототические обозночение порядка роста функции: О-обозночение,Ω-обозначение,Ѳ-обозночене

Верхняя асимптотическая граница, предоставляемая О-обозначениями, может описывать асимптотическое поведение функции с разной точностью. Граница дает правильное представление об асимптотическом поведении функции, а граница его не обеспечивает. Для обозначения того, что верхняя граница не является асимптотически точной оценкой функции, применяются о-обозначения. Приведем формальное определение множества о(g(n)) (произносится как "о малое от g от n"):

Например: , но . Определения О-обозначений и о-обозначений похожи друг на друга. Основное отличие в том, что определение f(n) = О(g(n)) ограничивает функцию f(n) неравенством лишь для некоторой константы с > 0, а определение f(n) = о(g(n)) ограничивает ее неравенством для всех констант с > 0. Интуитивно понятно, что в о-обозначениях функция f(n) пренебрежимо мала по сравнению с функцией д(п), если п стремится к бесконечности, т.е:

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

Аналогично тому, как в О-обозначениях дается асимптотическая верхняя граница функции, в -обозначениях дается ее асимптотическая нижняя граница.Для данной функции g(n) выражение (произносится "омега большое от g от n" или просто "омега от g от n") обозначает множество функций, таких что

Для всех n, лежащих справа от , значения функции f(n) больше или равны значениям сg(n). Поскольку -обозначения используются для определения нижней границы времени работы алгоритма в наилучшем случае, они также дают нижнюю границу времени работы алгоритма для произвольных входных данных.

Для некоторой функции запись обозначает множество функций:

Функция принадлежит множеству , если существуют положительные константы и , позволяющие заключить эту функцию в рамки между функциями и для достаточно большихn. Поскольку — это множество, то можно написать . Это означает, что функция f(n) принадлежит множеству (другими словами, является его элементом). Обычно используется эквивалентная запись .
Для всех значений п, лежащих справа от , функция f(n) больше или равна функции , но не превосходит функцию .Другими словами, для всех функция f(n) равна функции g(n) с точностью до постоянного множителя. Говорят, что функция g(n) является асимптотически точной оценкой функции f(n).
Согласно определению множества в , необходимо, чтобы каждый элемент этого множества был асимптотически неотрицателен. Это означает, что при достаточно большихn функция f(n) является неотрицательной. (Асимптотически положительной называется такая функция, которая является положительной при любых достаточно больших п). Следовательно, функция g(n) должна быть асимптотически неотрицательной, потому что в противном случае множество в (g(n)) окажется пустым. Поэтому будем считать, что все функции, используемые в -обозначениях, асимптотически неотрицательные. Это также справедливо для других асимптотических обозначений.
Интуитивно понятно, что при асимптотически точной оценке асимптотически положительных функций, слагаемыми низших порядков в них можно пренебречь, поскольку при больших n они становятся несущественными. Даже небольшой доли слагаемого самого высокого порядка достаточно для того, чтобы превзойти слагаемые низших порядков. Таким образом, для выполнения неравенств, фигурирующих в определении -обозначений, достаточно в качестве выбрать значение, которое несколько меньше коэффициента при самом старшем слагаемом, а в качестве — значение, которое несколько больше этого коэффициента. Поэтому коэффициент при старшем слагаемом можно не учитывать, так как он лишь изменяет указанные константы.
Поскольку любая константа — это полином нулевой степени, то постоянную функцию можно выразить как или . Однако последнее обозначение не совсем точное, поскольку непонятно, по отношению к какой переменной исследуется асимптотика. Мы часто будем употреблять для обозначения либо константы, либо постоянной функции от какой-нибудь переменной.