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

 

Время выполнения программы описывается некоторой функцией от длины входа . Формула для описания функции может быть достаточно сложной, разные составляющие этой формулы по-разному влияют на скорость ее роста. Элемент, который определяет поведение формулы, называется ее главным членом. Для больших значений доминирует эффект главного члена, для малых начинают оказывать влияние другие факторы, поэтому сравнение алгоритмов становится более сложным, и обычно достаточно иметь упрощенный вариант формулы для того чтобы понять ее поведение при возрастании ее аргумента. Учет только главного члена позволяет разбивать множество функций на классы эквивалентности, вводить иерархии на классах функций, и тем самым сравнивать множества задач по сложности их решения.

Для описания асимптотических оценок имеется система нотаций:

§ Говорят, что f(n)= O (g(n)), если существует такая константа c>0 и такое число n₀, что выполняется условие 0≤f(n)≤c*g(n) для всех n≥n₀. Более формально:

O (g(n)) используется для указания функций, которые не более чем в постоянное число раз не превосходятg(n), этот вариант используется для описания оценок сверху (в смысле «не хуже чем»).

§ Говорят, что f(n)= W (g(n)), если существует такая константа c>0 и такое число n₀, что выполняется условие 0≤c*g(n)≤f(n) для всех n≥n₀. Более формально:

W (g(n)) используется для указания функций, которые не менее чем в постоянное число раз превосходят g(n), этот вариант необходим для описания оценок снизу (в смысле «не лучше чем»).

Следующее определение объединяет предыдущие случаи:

§ Говорят, что f(n)= Q (g(n)), если найдутся такие константы c₁,c₂>0 и такое число n₀, что для всех n≥n₀ выполняется условие 0≤c₁*g(n)≤f(n)≤c₂*g(n). В этом случае, говорят - функция g(n) является асимптотически точной оценкой для f(n).

Q (g(n)) используется для указания функций того же порядка, что и g(n), этот вариант используется для описания асимптотически точных оценок.

Асимптотические сравнения обладают некоторыми свойствами отношений действительных чисел:

Транзитивность

Из f(n)= Q (g(n)) и g(n)= Q (h(n)) следует f(n)= Q (h(n)).

Из f(n)=O(g(n)) и g(n)= O (h(n)) следует f(n)= O (h(n)).

Из f(n) = W (g(n)) и g(n) = W (h(n)) следует f(n) = W (h(n)).

Рефликсивность

Из f(n)= Q (f(n)).

Из f(n)= O (f(n)).

Из f(n) = W (f(n)).

Симметричность

f(n)= Q (g(n)) справедливо тогда и только тогда, когда g(n)= Q (f(n)).

Перестановочная симметрия

f(n)=O(g(n)) справедливо тогда и только тогда, когда g(n)= W (f(n))

Как ведут себя значения приведенных выше функций в зависимости от размера решаемых задач демонстрирует таблица

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

Границы размера задач, определяемых скоростью роста сложности

Несмотря на то, что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную, чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют.Например, предположим, что временные сложности алгоритмов и в действительности равны соответственно 1000n, 100n log n, 10 , и 2". Тогда будет наилучшим для задач размера , —для задач размера , —при , а — при n>1024.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Читайте также:

Асимптотические соотношения

Воспользуйтесь поиском по сайту: