ВУЗ:
Составители:
56
9. СЛОЖНОСТЬ АЛГОРИТМОВ
Рассмотрим задачу нахождения максимального элемента массива
среди n элементов x[1], x[2], …, x[n].
Пусть переменная m обозначает максимальный элемент массива, пе-
ременная k – порядковый номер элемента массива и переменная j – номер
максимального элемента массива. Тогда:
][][max
1
jxkxm
nk
==
≤≤
.
Предположим, что значение j при этом должно быть максимально воз-
можным.
Поставленная задача отыскания максимального элемента в массиве
может быть решена с помощью алгоритма М, блок-схема которого изо-
бражена на рис. 27.
Рис. 27. Блок-схема алгоритма
Проследим за работой этого алгоритма с использованием модели
памяти ЭВМ на следующем примере исходных данных:
n j k m x
5 5 4 7 6 10 7 8 7
4 3 8
1 2 3 4 5
2 2 10
1
0
Здесь блок M4 алгоритма был выполнен два раза.
В общем случае анализ сложности алгоритма включает в себя ана-
лиз затрачиваемой памяти и анализ времени работы. Заметим, что анализ
сложности нескольких алгоритмов, предназначенных для решения одной
j ← n, k ← n − 1, m ← x[n]
Начало
Конец
k = 0
x[k] ≤ m
Нет Да
j ← k, m ← x[k]
Нет
k ← k − 1
Да
M1
M2
M3
M4
M5
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
