Теория алгоритмов. Зюзысов В.М. - 56 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Сравнение роста функций
Определение. Говорят, что функция g мажорирует функцию f, если f(n) = O(g(n)).
Символ O(g(n)) читается как «O большое от g(n)»; при этом говорят, что f(n) имеет
порядок O большое от g(n).
Отношение «O большое» наиболее полезно для сравнения асимптотического роста
функции. Рассмотрим это отношение для конкретных функций.
Для положительных целых чисел r и s следующую теорему можно доказать
методом индукции. Справедливость утверждения теоремы для положительных
рациональных чисел r и s можно показать, не используя логарифмы.
Теорема 27. Если r и s – действительные числа
, r ≤ s и n > 1, тогда n
r
≤ n
s
.
Следовательно, n
r
= O(n
s
).
Доказательство. Функция ln(x) – возрастающая, поэтому a≤b тогда и только тогда,
когда ln(a) ≤ ln(b). Отсюда n
r
≤ n
s
тогда и только тогда, когда ln(n
r
) ≤ ln(n
s
), что, в свою
очередь, выполняется тогда и только тогда, когда r ln(n) ≤ s ln(n), т.е. тогда и только тогда,
когда r ≤ s, поскольку ln(n) для n > 1 – величина положительная.
Следующие теоремы показывают, что свойство функции иметь порядок O(g(n))
замкнуто относительно операций сложения и умножения на число.
Теорема 28. Если f(n) = O(g(n)), то cf(n) = O(g(n)).
Доказательство. По определению, |f(n)| ≤ k |g(n)| для некоторого действительного
числа k и всех n, больших или равных некоторому целому числу m. Поэтому
|cf(n)| ≤ k|c| |g(n)|
и cf(n) = O(g(n)).
Теорема 29. Если f(n) = O(g(n)) и h(n) = O(g(n)), то (f+h)(n) = O(g(n)).
Доказательство. По определению, для некоторого постоянного k и некоторого
целого числа m
1
имеем |f(n)| ≤ k |g(n)| для всех n > m
1
. Опять же по определению, для
некоторого постоянного l и некоторого целого числа m
2
имеем |h(n)| ≤ l |g(n)| для всех n >
m
2
. Пусть m = max(m
1
, m
2
). Следовательно, для всех n > m
|f(n)+h(n)| ≤ |f(n)|+|h(n)| ≤
≤ k |g(n)| + l |g(n)| =
= (k + l)|g(n)|
и (f+g)(n) = O(g(n)).
Теорема 30. Если f(n) = O(g(n)) и h(n) = O(e(n)), то (f×h)(n
) = O(g×e)(n)).
Доказательство. По определению, для некоторого постоянного k и некоторого
целого числа m
1
имеем |f(n)| ≤ k |g(n)| для всех n > m
1
. Опять же по определению, для
некоторого постоянного l и некоторого целого числа m
2
имеем |h(n)| ≤ l |e(n)| для всех n >
m
2
. Пусть m = max(m
1
, m
2
). Следовательно, для всех n > m
|f(n)×h(n)| = |f(n)|×|h(n)| ≤
≤ k |g(n)| l |e(n)| =
= (k l)|g(n)×e(n)|
и (f×g)(n) = O(g×e)(n)).
Следующая теорема устанавливает мажоранту для полинома.
Теорема 31. Если p(n) = a
k
n
k
+ a
k-1
n
k-1
+ … + a
1
n + a
0
, то p(n)=O(n
k
).
Доказательство.
|p(n)| ≤ |a
k
n
k
+ a
k-1
n
k-1
+ … + a
1
n + a
0
| ≤
(в силу неравенства треугольника: |A+B|≤ |A|+|B|)

Страницы