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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

76
необходимо выполнить по крайней мере (N – 1) сравнений. Но, заметим,
что это справедливо только к первому выбору. При последующих выборах
можно использовать извлечённую ранее информацию.
Рассмотрим те самые шестнадцать ключей, которые разобьём на че-
тыре группы по четыре числа и найдём максимальный элемент в каждой
группе, выполнив при этом 12 сравнений. Наибольший элемент 908 из
максимальных элементов в группах 512, 908, 653, 765 найдём путём вы-
полнения трёх сравнений:
908
512 908 653 765
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
Следовательно, на определение наибольшего элемента 908 во всём
файле затрачивается 15 сравнений.
Для получения второго по величине элемента 897 в файле достаточ-
но определить максимальный элемент из оставшихся трёх элементов 170,
897, 275 во второй группе, выполнив при этом два сравнения, и найти
наибольший из элементов 512, 897, 653, 765 за три сравнения:
897
512 897 653 765
503
87
512
61
170
897
275
653
426
154
509
612
677
765
703
Таким образом, на определение второго по величине элемента 897
затрачивается всего пять сравнений.
Для определения третьего по величине элемента достаточно найти
максимальный из элементов 170, 275 и наибольший из элементов 512,
275, 653, 765. Третий по величине элемент 765 определяется за четыре
сравнения и т.д.
В общем случае, если N является точным квадратом некоторого на-
турального числа, то файл можно разделить на
N
групп по
N
эле-
ментов в каждой группе. Тогда любой выбор, кроме первого, потребует
не более чем (
N
– 1) сравнений внутри группы ранее выбранного эле-
мента плюс (
N
– 1) сравнений среди «лидеров» групп. Этот метод по-
лучил название квадратичного выбора, общее время работы которого
имеет порядок N
N
, что существенно лучше, чем N
2
.
Метод квадратичного выбора можно обобщить и получить в резуль-
тате метод выбора третьей, четвёртой, …, n-й степени. Например, в мето-
де кубического выбора файл разбивается на
3
N
больших групп, каждая
из которых содержит по
3
N
малых групп по
3
N
записей. Время рабо-
ты кубического выбора пропорционально N
3
N
.

Страницы