Методы программирования. Громов Ю.Ю - 59 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

59
Опуская вывод зависимостей для математического ожидания ave A и
квадратичного отклонения dev A при произвольном значении n, запишем
статистические характеристики случайной величины А в виде:
A = (min 0, ave (H
n
– 1), max (n – 1), dev
)2(
nn
HH −
),
где H
n
=
∑
=
n
k
k
1
1
− гармонический числовой ряд,
)2(
n
H
=
∑
=
n
k
k
1
2
1
− гармониче-
ский числовой ряд второго порядка.
Подтверждая полученные ранее значения математического ожидания
и квадратичного отклонения случайной величины А при n = 3, получим:
H
3
– 1 =
∑
=
3
1
1
k
k
– 1 = 1 +
2
1
+
3
1
– 1 =
2
1
+
3
1
=
6
5
;
)2(
3
H
=
∑
=
3
1
2
1
k
k
= 1 +
2
2
1
+
2
3
1
= 1 +
4
1
+
9
1
= 1
36
13
;
)2(
3
3
HH
−
=
36
13
1
6
5
1 −
=
36
17
≈ 0,69.
Время работы алгоритма М для решения рассматриваемой задачи
отыскания максимального элемента в массиве можно оценить по значе-
нию выражения (7 + 5 n + 4 A) u, где u – время выполнения одного такта
гипотетической вычислительной машиной MIX.
Упражнения
1. Оцените минимальное, максимальное и среднее время работы
алгоритма M при n = 5, если этот алгоритм выполняет гипотетическая
машина MIX.
10. СОРТИРОВКА. ВНУТРЕННЯЯ СОРТИРОВКА.
СОРТИРОВКА ПОДСЧЁТОМ
Под сортировкой будем понимать переразмещение некоторых объ-
ектов в возрастающем или убывающем порядке. Сортировка может быть
использована в различных случаях, например, для:
а) решения задачи «группировки», когда нужно собрать вместе все
элементы с одинаковым значением некоторого признака. Эту задачу
можно решить, расположив элементы в неубывающем порядке;
б) отыскания общих элементов в двух или более файлах. Отсорти-
ровав все файлы в одном и том же порядке, можно отыскать в них все
общие элементы за один последовательный просмотр без возвратов;

Страницы