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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

≤ |a
k
n
k
| + |a
k-1
n
k-1
| + … + |a
1
n| + |a
0
| =
= |a
k
|
n
k
+ |a
k-1
|
n
k-1
+ … + |a
1
|n + |a
0
| ≤
(по теореме 1)
≤ |a
k
|
n
k
+ |a
k-1
|
n
k
+ … + |a
1
| n
k
+ |a
0
| n
k
=
= (|a
k
|
+ |a
k-1
|
+ … + |a
1
| + |a
0
|) n
k
и p(n)=O(n
k
).
Теорема 32. Для целых чисел a и b, больших единицы, log
a
(n) = O(log
b
(n)).
Доказательство. Следует непосредственно из равенства
)(log
)(log
)(log
b
n
n
a
b
a
=
.
Теорема 33. Пусть n – неотрицательное целое число. Тогда n < 2
n
и, следовательно,
n = O(2
n
).
Доказательство. Воспользуемся индукцией, имея для n = 0, 0 < 2
0
= 1. Допустим,
что k < 2
k
, тогда
k+1 ≤ k+k ≤ 2
k
+ 2
k
= 2
k+1
и, по индукции, n < 2
n
.
Пусть R – отношение на множестве функций, определенное как fRg, если f(n) =
O(g(n)). Очевидно, отношение R рефлексивно. Приведенная ниже теорема утверждает, что
это отношение также и транзитивно. Доказательство теоремы предоставляется читателю.
Теорема 34. Если f(n) = O(g(n)) и g(n) = O(h(n)), то f(n) = O
(h(n)).
Следующая теорема дает ответ на вопрос о том, какие функции могут выступать в
роли мажорант для других функций.
Теорема 35. Для целых чисел a, больших единицы, log
a
(n) = O(n).
Доказательство. Согласно теореме 33, имеет место неравенство n < 2
n
. Поэтому
log
2
(n) < log
2
(2
n
) = n и log
2
(n) = O(n). Поскольку по теореме 32 имеем log
a
(n) = O(log
2
(n)),
то по теореме 34 получаем log
a
(n) = O(n).
Доказательство сформулированных ниже теорем предоставляем читателям.
Теорема 36. Пусть n – неотрицательное целое число, тогда n! < n
n
и,
следовательно, n! = O(n
n
).
Теорема 37. Пусть a > 1 и n – неотрицательное целое число, тогда log
a
(n!) ≤ n
log
a
(n) и, следовательно, log
a
(n!) = O(n log
a
(n)).
Пример 1. Определим число арифметических операций, необходимых для
сложения двух матриц.
Пусть матрицы имеют размеры m×k. Тогда алгоритм сложения матриц A + B = C
можно описать на Паскале следующим образом:
for i:=1 to m do
for j:= 1 to k do
C[
i,j]:=A[i,j] + B[i,j];
Как видим, сложение выполняется для каждого i и каждого j. Поскольку i принимает m
значений, а j принимает k значений, то выполняется mk операций сложения. Пусть n =
max (m, k). Тогда число выполняемых арифметических операций имеет порядок O(n
2
).
Пример 2. Определим число арифметических операций, необходимых для
умножения двух матриц.
Пусть матрицы A и B имеют размеры m×p и p×k, соответственно. Тогда алгоритм
умножения матриц A × B = C можно описать на Паскале следующим образом:
for i:=1 to m do
for j:= 1 to k do
begin

Страницы