Элементы дискретной математики - 42 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

42
Асимптотики
Асимптотики – это искусство оценивания и сравнения скоростей роста функций.
Нередко в задачах на нахождение общего решения рекуррентного соотношения не требуется
точное значение n-го члена, чаще бывает достаточной оценка порядка, а иногда требуется
только оценка скорости роста функции f(n). Для описания роста функции используется О-
символика. (
ввел Поль Бахман в 1894 г.)
Запись f(n)=O(g(n)) означает, что существуют положительные константы M и n
0
, такие, что
)()( ngMnf ⋅≤ , для всех целых n≥n
0
.
Пример1.
Для рекуррентного соотношения f(n)=5f(n–1)–6f(n–2), с начальными членами f(1)=0 и
f(2)=13 общее решение имеет вид f(n)=2
n
+3
n
. Можно сказать, что f(n)=O(3
n
).
Докажем это. Здесь M=2, а n
0
=1.
Неравенство 2
n
+3
n
≤3
n
+3
n
верно для всех n≥1
3
n
+3
n
=2·3
n
, значит, 2
n
+3
n
≤2·3
n
, следовательно, f(n)=O(3
n
)
Пример2.
Для последовательности Фибоначчи, как было доказано выше, формула общего члена
имеет вид:
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
+
=
nn
n
f
2
51
2
51
5
1
. Легко доказать, что f
n
=O(2
n
).
Соотношение f(n)=O(g(n)) называют асимптотическим соотношением, оно означает,
что функция f(n) растет не быстрее, чем функция g(n). Определены еще два асимптотических
отношения.
Определение 1. Функция f(x) асимптотически равна (эквивалентна) g(x) (обозначается
f(x)∼g(x)) при x→x0, если lim (f(x)/g(x))=1.
Если функция f(x) эквивалентна g(x), то это означает, что f(x) растет с такой же
скоростью, как и g(x).
Определение 2. f(x)=o(g(x)) при x→x0, если lim (f(x)/g(x))=0.
Если f(x)=o(g(x)), то это означает, что функция f(x) растет медленнее, чем g(x).
Замечание.

Страницы