ВУЗ:
Составители:
57
и той же задачи, позволяет выбрать среди них наилучший алгоритм (наи-
меньшей сложности).
Приведённый выше алгоритм М тривиален, но, тем не менее, на его
примере удобно проиллюстрировать детальный анализ алгоритма на
сложность.
Отметим, что перед началом работы этого алгоритма необходимо
выделить место в оперативной памяти для хранения значений перемен-
ных j, k, m, n и массива x, а в ходе его выполнения дополнительное место
в памяти не требуется. Поэтому, с точки зрения анализа затрачиваемой
памяти, для алгоритма М достаточно запоминающего устройства неко-
торого фиксированного объёма.
Сосредоточим основное внимание на анализе времени работы алго-
ритма М и оценим вначале, сколько раз будет выполнен каждый его шаг:
Шаг Число выполнений
M1
M2
M3
M4
M5
1
n
n − 1
A
n − 1
Заметим, что здесь символом А обозначено число замен значений те-
кущего максимума, которое является неизвестной случайной величиной,
зависящей от конкретных значений элементов массива x[1], x[2], …, x[n].
Поскольку время работы алгоритма М зависит от случайной величины А,
анализ заключается в нахождении: минимального, максимального и
среднего значения величины А, а также квадратичного отклонения вели-
чины А.
Минимальное значение величины А равно нулю. Это случай, когда
][max][
1
kxnx
nk≤≤
= .
Максимальному значению n − 1 величина А равна в случае, когда
x[1] > x[2] > … > x[n]. Среднее значение величины А находится между
минимальным и максимальным значениями.
Рассмотрим всевозможные случаи соотношений между значениями
элементов массива и соответствующие значения величины А при усло-
вии, что n = 3.
Случай Значение А Случай Значение А
x[1] < x[2] < x[3]
0 x[2] < x[3] < x[1]
1
x[1] < x[3] < x[2]
1 x[3] < x[1] < x[2]
1
x[2] < x[1] < x[3]
0 x[3] < x[2] < x[1]
2
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »
