Асимптотические представления и анализ алгоритмов

Очень часто для сравнения величин достаточно знать их приближенные значения. Для примера приведем гармонический ряд Hn=1+1/2+1/3+…+1/n=Σ1/k.

Hn→∞ очень медленно и всегда больше любого заданного числа. Точное значение можно вычислить только для конечного n.

H≈ln(n)+γ+1/2n-1/12n^2+1/120n^3-1/252n^4+…, где γ=0.5772156 – постоянная Эйлера

Из этого следует, что Hn близко к ln(n) при больших n.

Для анализа алгоритмов по времени выполнения используют обозначение O(f(n)), введенное в 1892 году П.Бахманом, которое позволяет заменять знак “≈” на “=”. Такое обозначение можно использовать всегда, когда n - целое и точное значение f(n) неизвестно.

Hn = ln(n)+y+O(1/n)

12 + 22 + 32 + … + n2 = (1/3)n(n+1/2)(n+1)=(1/3)n3 + (1/2)n2 + (1/6)n

1 + 22 + 32 + … + n2 = O(n3) или более точно (1/3)n3 + O(n2)

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

С некоторой осторожностью с этим символом можно оперировать по обычным арифметическим правилам.

Есть важное различие в односторонности равенства с символом О.

О(n2)=(1/2)n2 + n не имеет смысла, т.к. левая часть несет меньше смысла, чем правая.

Символ О часто используется для оценки времени выполнения алгоритма или количества итераций.

С символом О можно проводить операции:

f(n) = O(fn)

c*O(fn)=O(fn), где с = const

O(fn)+O(fn)=O(fn)

O(O(fn))=O(fn)

O(fn)*O(gn)=O(fn*gn)=fn*O(gn)