Главная Промышленная автоматика.

требования к контрпримеру. Пусть средняя гдубина дистьев поддерева Ту состав-дяет logfei, а средняя гдубина дистьев поддерева - logfea- Тогда средняя гдубина дистьев дерева Т равна

Поскольку ky + =к, топосдеднее выражение можно переписать так:

i(fe.log(2ft,)+fe,log(2fe,)). (8.13)

Легко проверить, что при 1=3= ft/2 выражение (8.13) принимает значение logft. Теперь читатель должен показать, что выражение (8.13) при выполнении условия ky + к2 = к имеет минимум, когда fti = fej. Это несложное упражнение для читателя, знакомого с дифференциальным исчислением. Так как минимум выражения (8.13) равен logfe, то можно считать доказанным, что контрпример дерева Т со средней глубиной дистьев, меньшей чем logft, не сушествует.

8.7. Порядковые статистики

Задача вычисления порядковых статистик заключается в следующем: дан список из п записей и целое число к, необходимо найти ключ записи, которая стоит в списке, отсортированном в возрастаюшем порядке, в fe-й позиции. Для краткости эту задачу будем называть "задачей нахождения ft-й порядковой статистики". Специальные случаи этой задачи возникают при к = 1 (нахождение минимального элемента), к = п (нахождение максимального элемента) и, если п нечетно, к = (п + 1)/2 (нахождение медианы).

В некоторых случаях решение задачи вычисления порядковых статистик находится за линейное время. Например, нахождение минимального элемента (как и максимального) требует времени порядка 0(л). Как упоминалось при изучении пирамидальной сортировки, если к < и/logn, тогда для нахождения ft-й порядковой статистики можно построить кучу (за время порядка 0(л)) и затем выбрать из нее к наименьших эдементов за время 0(п + к logre) = 0(л). Подобным образом при к > п - n/logn также можно найти порядковую статистику за время 0(ге).

Вариант быстрой сортировки

По-видимому, самым быстрым в среднем способом нахождения ft-й порядковой статистики является рекурсивное применение процедуры, основанной на методе быстрой сортировки. Назовем эту процедуру select (выбор). Процедура select(i. j, к) находит ft-й эдемент среди эдементов A[i], A[j], которые взяты из некоторого большого массива А[ге]. Процедура select выполняет следующие действия.

1. Назначает опорный эдемент, скажем v.

2. Используя процедуру partition из дистинга 8.7, разделяет элементы A[i], А[[\ на две группы. В первой группе A[i], ...,А[т - 1] значения ключей всех записей меньше v, во второй группе А[т], А[у]- равны иди больше v.

3. Если к < т - i, тогда fe-й эдемент находится в первой группе и к ней снова применяется процедура select(i, т - \, к). Если к > т - i, тогда вызывается процедура select{m,}, к - т + i).

Рано иди поздно вызов процедуры select(i, j, к) будет сделан для эдементов A[i}, АЦ], имеющих одинаковые значения ключей (и поэтому скорее всего будет i = j). Значение ключа этих эдементов и будет искомым значением fe-й порядковой статистики.



Так же, как и метод быстрой сортировки, процедура select (так как она описана выще) в самом худщем случае потребует времени не менее П(ге). Например, если при поиске минимального элемента в качестве опорного элемента всегда брать наиболь-щее из возможных значений ключей, то получим для этой процедуры время выполнения порядка О(л). Но в среднем процедура select работает значительно быстрее, чем алгоритм быстрой сортировки, в среднем она выполняется за время 0{п). Принципиальная разница между этими алгоритмами заключается в том, что когда процедура быстрой сортировки вызывается два раза, процедура select в аналогичной ситуации вызывается только один раз. Можно провести анализ процедуры select теми же методами, которые применялись при анализе алгоритма быстрой сортировки, но чтобы избежать сложных математических выкладок, здесь мы ограничимся только интуитивными соображениями, показывающими среднее время выполнения процедуры select. Эта процедура повторно вызывает себя на подмножестве, которое является только частью того множества, для которого она вызывалась на предыдущем щаге. Сделаем умеренное предположение, что каждый вызов этой процедуры осуществляется на множестве элементов, которое составляет 9/10 того множества, для которого был произведен предыдущий вызов процедуры. Тогда, если обозначить через Т(п) время, затрачиваемое процедурой select на множестве из п элементов, для некоторой константы с будем иметь

Т(п)<Т(пУгсп. (8.14)

Используя технику из следующей главы, можно показать, что рещением неравенства (8.14) будет Т(п) = 0(п).

Линейный метод нахождения порядковых статистик

Чтобы гарантировать для процедуры, подобной select, в самом худщем случае время выполнения порядка 0(п), необходимо показать, что за линейное время можно выбрать такой опорный элемент, который разбивает множество элементов на два подмножества, размер которых не больще некоторой фиксированной доли исходного множества. Например, рещение неравенства (8.14) показывает, что если опорный элемент не меньще (ге/10)-го порядкового элемента и не больще (9л/10)-го порядкового элемента, тогда множество, для которого вызывается процедура select, разбивается на подмножества, не превыщающие 9/10 исходного множества, и это гарантирует линейное время в самом худщем случае.

Нахождение "хорощего" опорного элемента можно осуществить посредством следующих двух щагов.

1. Выполняется разделение п элементов на группы по 5 элементов, оставляя в стороне группу из 1 - 4 элементов, не вощедщих в другие группы. Каждая группа из 5 элементов сортируется любым алгоритмом в порядке возрастания и берутся средние элементы из каждой группы. Всего таких средних элементов будет [л/5].

2. Используя процедуру select, находится медиана этих средних элементов. Если [л/5] - четно, то берется элемент, наиболее близкий к середине. В любом случае будет найден элемент, стоящий в позиции [(л -i- 5)/10] отсортированного списка средних элементов.

Если среди записей не слищком много таких, значения ключей которых совпадают со значением опорного элемента, тогда значение опорного элемента достаточно далеко от крайних значений ключей. Для простоты временно положим, что все значения ключей различны (случай одинаковых ключевых значений будет рассмотрен ниже). Покажем, что выбранный опорный элемент (являющийся [(л -i- 5)/10]-м порядковым элементом среди [га/5] средних элементов) больще не менее 3[(л - 5)/10] элементов из га исходных элементов. В самом деле, опорный элемент больще [(л - 5)/10] средних элементов. В свою очередь каждый из этих средних элементов больще двух элементов из той



пятерки элементов, которой он принадлежит. Отсюда получаем величину 3[(я - 5)/10]. Если га > 75, тогда 3[(ге - 5)/10] не меньше ге/4. Подобным образом доказывается, что выбранный опорный элемент меньше или равен не менее 3[(ге - 5)/10] элементов. Отсюда следует, что при « > 75 выбранный опорный элемент находится между первой и последней четвертями отсортированного списка исходных элементов.

Алгоритм нахождения fe-й порядковой статистики в виде функции select показан в листинге 8.14. Как и в алгоритмах сортировки, предполагаем, что список исходных элементов представлен в виде массивам! записей типа recordtype и что записи имеют поле key типа key type. Нахождение fe-й порядковой статистики выполняется, естественно, посредством вызова функции selectil, п, к).

Листинг 8.14. Линейный алгоритм нахождения /г-й порядковой статистики

function select (i, j, к: integer ): keytype;

{ Функция возвращает значение ключа к-то элемента из A[i] , ----Alj] }

т; integer; { используется в качестве индекса } begin

(1) if J - 1 < 74 then begin

{ элементов мало, select рекурсивно не применяется }

(2) сортировка Л[1], A[j] простым алгоритмом;

(3) retum([i + к - 1].кеу) end

else begin { select применяется рекурсивно }

(4) for m:= О to (j - i - 4) div 5 do

{ нахождение средних элементов в группах из 5-ти элементов }

(5) нахождение 3-го по величине элемента в группе

A[i + Ъ*т\, Л[1 + 5*т + 4] и

перестановка его с A[i + га];

(6) pivot:= select а, i+div 5,{j-i-4) div 10);

{ нахождение медианы средних элементов }

(7) га: = parti tJon (i, /", pivot);

(8) if к <= m - i then

(9) return(select(i, m - 1. k)) else

(10) return(select (ui, j, к - (m - i) ) )

end; { select }

Для анализа времени выполнения процедуры select из листинга 8.14 положим здесь, что j - i + \ = га. Строки (2), (3) выполняются, если п не превосходит 74. Поэтому, если даже выполнение строки (2) требует времени порядка 0(п)в обшем случае, здесь потребуется конечное время, не превосходяшее некоторой константы с. Таким образом, при « < 74 строки (1) - (3) требуют времени, не превосходяшего некоторой константы Су.

Теперь рассмотрим строки (4) - (10). Строка (7), разбиение множества элементов по опорному элементу, имеет время выполнения 0(п), как было показано при анализе алгоритма быстрой сортировки. Тело цикла (4), (5) выполняется п/5раз, упорядочивая за каждую итерацию 5 элементов, на что требуется фиксированное время. Поэтому данный цикл выполняется за время порядка 0(п).

Обозначим через Т(п) время выполнения процедуры select на п элементах. Тогда строка (6) требует времени, не превышаюшего (п/б).Поскольку строку (10) можно достигнуть только для га > 75, а, как было показано ранее, при п > 75 количество элементов, меньших опорного элемента, не превышает Зга/4. Аналогично, количество





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 [82] 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018