Составители:
Рубрика:
43
В соотношениях, использующих О-символику, левые и правые части не
симметричны: правая часть всегда содержит меньше информации, чем левая, и
поэтому нельзя в любом контексте заменять левую часть выражения правой.
Например, из двух корректных асимптотических равенств х=О(х
2
) и х
2
=О(х
2
) не
следует, что х=х
2
.
Примеры.
1.
Полином асимптотически равен своему старшему члену:
при х→∞.
2.
Полином f(n)=2n
5
+6n
4
+6n
2
+18 есть О(n
5
).
3.
Функция f(n)=2
n
есть O(2
n+1
) и o(5
n+1
).
4.
Для линейного рекуррентного соотношения общее решение имеет вид:
f(n)=С
1
r
1
n
+C
2
r
2
n
+…+C
k
r
k
n
. Если нас интересует только асимптотическое поведение
последовательности, то достаточно рассмотреть лишь члены Ci(
r
i
)
n
, у которых r
i
имеет
максимальное абсолютное значение среди тех членов, у которых Ci≠0.
Существуют оценки и асимптотики для комбинаторных чисел. Наиболее известна
асимптотика для чисел n!, называемая формулой Стирлинга: n! ∼
nn
enn
−
π
2.
О-символику используют также для оценки сложности алгоритма. Одной из важнейших
характеристик алгоритма является его временная сложность в худшем случае.
Пусть некоторая задача имеет размерность n (например, длина массива при сортировке). Обозначим
через t(n) максимальное число действий, необходимое для решения задачи. Под действием понимают
выполнение «простой» операции – любой арифметической операции, операции сравнения, присваивания
и т. п.
При этом сложность алгоритма зависит от конкретного вида команд. Поэтому при оценке интересует лишь
асимптотическая сложность алгоритма, то есть порядок роста сложности при условии, что размер задачи
неограниченно возрастает.
Алгоритм считается достаточно хорошим, если сложность этого алгоритма есть О(n
k
) при некотором
k>0. В таком случае говорят, что задача может быть решена за полиномиальное время, а сам алгоритм
называется полиномиальным.
)(
0
ni
n
i
i
xOxa =
∑
=
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
