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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

C[i,j]:=0;
for s:= 1 to p do
C[
i,j]:= C[i,j]+A[i,s]* B[s,j];
end;
Поскольку s принимает значения от 1 до p, то выполняется p операций сложения и p
операций умножения. Величина s изменяется от 1 до p для каждого i и каждого j, поэтому
s пробегает значения от 1 до p mk раз. Таким образом, выполняется mkp операций
сложения и столько же операций умножения. Следовательно, всего
выполняется 2mkp
операций. Пусть n = max(m,k,p). Тогда число выполняемых арифметических операций
имеет порядок O(n
3
).
Пример 3. Сравним количество операций, которое требуется для
непосредственного вычисления значения многочлена традиционным способом и по схеме
Горнера.
Пусть требуется вычислить p(c), где p(x) = a
n
x
n
+ a
n–1
x
n–1
+ … + a
1
x + a
0
. Если p(c)
вычисляется непосредственно, то для подсчета c
k
требуется выполнить k–1 операций
умножения. Еще одна операция нужна для умножения на a
k
, так что вычисление a
k
x
k
требует k операций умножения. Таким образом, нужно выполнить 1 + 2 + …+ n = n(n-1)/2
умножений. Для того чтобы найти сумму n+1 слагаемых, требуется выполнить n
сложений, так что общее число арифметических операций равно n(n-1)/2 + n и имеет
порядок O(n
2
).
При вычислении полинома a
4
x
4
+ a
3
x
3
+ a
2
x
2
+ a
1
x + a
0
по схеме Горнера, мы
переписываем полином в виде x(x(x(a
4
x+ a
3
) + a
2
) + a
1
) + a
0
и замечаем, что выражение
включает четыре операции умножения и четыре операции сложения. Очевидно, в общем
случае p(x) = x(x( … (x(a
n
x+a
n–1
) + a
n–2
) + … a
2
) + a
1
) + a
0
включает n операций сложения и
n операций умножения. Таким образом, общее число арифметических операций равно 2n
и имеет порядок O(n).
Задача. Расположите следующие функции в порядке увеличения скорости роста
(каждая функция есть O(следующая)), не исключено, что некоторые функции имеют
одинаковую скорость:
2
n
, (1+n)!, ln (n!), e
n
, n 2
n
, , 1, n (ln n), , (trunc(ln n))!, ln n, n
)ln(ln n
n
)2(
2
n
2
, ln (ln n),
nln
2
,
n!, e,
, , (ln n)
nln
4
)
1
2(
2
n+
2
, n, nln , , (3/2)
nln
2
n
, n
3
, ,
n
n
ln
)(ln
nln
2
.
5.2 Алгоритмы и их сложность
Класс однородных вычислительных задач мы будем называть проблемой (также
используется понятие массовая задача или абстрактная задача). Индивидуальные
случаи проблемы Q мы будем называть частными случаями проблемы Q. Мы можем,
например, говорить о проблеме умножения матриц. Частные случаи этой проблемы суть
пары матриц, которые нужно перемножить.
Более формально, мы принимаем
следующую абстрактную модель вычислительной
задачи. Абстрактная задача есть произвольное бинарное отношение Q между элементами
двух множеств – множества условий (или входных данных) I и множества решений S.
Например, в задаче умножения матриц входными данными являются две конкретные
матрицы – сомножители, а матрица – произведение является решением задачи. В задаче
SHORTEST-PATH (поиска кратчайшего пути между
двумя заданными вершинами
некоторого неориентированного графа G = (V,E)) условием (элементом I) является тройка,
состоящая из графа и двух вершин, а решением (элементом S) – последовательность
вершин, составляющих требуемый путь в графе. При этом один элемент множества I

Страницы