Выбор из дерева

Этот метод является выбором n-й степени, где n выбрано так, что размер самой малой группы минимален и равен 2.

i j Рассмотрим, например, результаты соревнований по настольному теннису:

Рис. 3 – Дерево выбора

Сидоров побеждает Володина, а Иванов побеждает Сергеева; затем в следующем туре Иванов выигрывает у Сидорова и т.д.

На этом рисунке показано, что Иванов – чемпион среди восьми спортсменов, а для того, чтобы определить это, потребовалось 8-1=7 матчей (т.е. сравнений).

Петров вовсе не обязательно будет вторым по силе игроком: любой из спортсменов, у которых выиграл Иванов (чемпион), включая даже проигравшего в первом туре Сергеева, мог бы оказаться вторым по силе игроком. Второго игрока можно определить, заставив сыграть Сергеева с Сидоровым, а победителя этого матча – с Петровым. Всего два матча требуется для определения второго по силе игрока, исходя из того соотношения сил, которое мы запомнили из предыдущих игр.

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Поиск наименьшего ключа из n элементов потребует n-1 сравнений, из (n-1) элементов – (n-2) сравнений.

Как можно улучшить эту сортировку выбором? Это можно сделать только в том случае, если получить от каждого прохода больше информации, чем просто указание на один наименьший элемент.

Например, с помощью n/2 сравнений можно определить наименьший элемент (ключ) из каждой пары, при помощи n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т.д. Наконец, при помощи n-1 сравнений можно построить дерево выбора и определить корень как наименьший ключ.

На втором шаге нужно спуститься по пути, указанному наименьшим ключом, и исключить его, последовательно заменяя либо на “дыру” (или ключ ∞), либо на элемент, находящийся на противоположной ветви промежуточного узла.

Элемент, оказавшийся в корне дерева, вновь имеет меньший ключ (среди оставшихся) и может быть исключён.

После n таких шагов дерево становится пустым (т.е. состоит из “дыр”) и процесс сортировки закончен.

Каждый из n шагов требует log₂n сравнений. Вся сортировка требует порядка n*log₂n элементарных операций, не считая n шагов которые необходимы для построения дерева.

Это значительное улучшение по сравнению с простым методом, требующим n² шагов. При сортировке с помощью дерева задача хранения информации стала сложнее и поэтому увеличилась сложность отдельных шагов. Для хранения возросшего объёма информации, получаемой на начальном проходе, нужно строить некоторую древовидную структуру.

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