Квадратичный выбор

Рассмотрим следующий метод: пусть файл содержит 16 записей. Разобьём его на четыре группы по четыре записи.

|| 14 5 18 21 || 2 7 11 3 || 9 26 1 8 || 13 22 6 20 ||

Найдём наибольшие элементы в каждой группе и соберём их вместе:

21 11 26 22

Тогда наибольший среди них и будет наибольшим в файле. Чтобы получить второй по величине элемент, достаточно просмотреть оставшиеся элементы группы, содержащей 26, т.е. максимальный, и максимум из них поместить в «группу лидеров» на место 26 и т.д.

Вообще, если N - точный квадрат, то можно разделить файл на √N групп по √N элементов в каждой. Тогда любой шаг, кроме первого, потребует не более, чем √N – 1 сравнений внутри группы раннее выбранного элемента плюс √N – 1 сравнений в “группе лидеров”. Этот метод получил название “квадратичный выбор”.

Оказывается такой метод может быть обобщён: существует метод кубического выбора (³√N больших групп, каждая из которых содержит ³√N малых групп по ³√N записей), выбора четвёртой степени и т.д. Если эту идею развить до её полного логического завершения, то мы придём к выбору n-й степени, основанному на структуре бинарного дерева.

Пример: Схема кубического выбора.

(n=27, ³√27=3);

max –максимальный элемент в выходную последовательность

Поиск по сайту: