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

Элементы, меньшие - и/ги pasmie т

L/7/5J упорядоченных [• пос/1едовате/1Ы10стей, лредстаемннык в виде столбцов с наименьшим I

З/гементом наверху \ \

------1

• • •!

1------

. • . {.

. . .!

г- ---5. - i

Элементы, большие .

или равные т

Последовательность М, изображенная в упорядоченном виде

Рис. 3.11. Разбиение S по алгоритму 3.6.

чиваемое на выбор й-го наименьшего элемента из последовательности длины п. Длина последовательности М, составленной из медиан подпоследовательностей, не больше п/5, и потому рекурсивный вызов процедуры ВЫБОР (f М/2 ~], М) занимает время, не большее Г (п/5).

Каждая из последовательностей 5i и 5з имеет длину не более Зп/4. Чтобы увидеть это, заметим, что не менее п/10 J элементов последовательности М. больше или равны т и для каждого из них найдутся в 5 два различных элемента, которые так же соотносятся с т.. Следовательно, 5in-31 п/10 J , т. е. при п50 длина последовательности 5i меньше Зп/4. Аналогичное рассуждение применимо и к 5з. Поэтому рекурсивный вызов в строке 10 или 12 занимает времени не более 7(Зп/4). Все остальные операторы тратят не более 0(п) времени. Таким образом, для некоторой постоянной с

( СП для ft < 49,

(3.8)

Г (п/5) + Г(Зп/4)+сп для п>50. Из (3.8) по индукции можно доказать, что 7(пХ20 сп.

3.7. СРЕДНЕЕ ВРЕМЯ ДЛЯ ПОРЯДКОВЫХ СТАТИСТИК

В этом разделе мы изучим среднее время, затрачиваемое на выбор k-ro наименьшего элемента в последовательности из п элементов. Мы увидим, что для нахождения k-ro наименьшего элемента требуется провести по меньшей мере п-1 сравнений как в худшем случае, так и в среднем. Поэтому выбирающий алгоритм, описанный в предыдущем разделе, с точностью до постоянного множителя оптимален в классе деревьев решений. Здесь мы приведем другой выбирающий алгоритм, который имеет квадратичную сложность в худшем случае,



НО среднее время работы которого составляет лишь долю времени работы алгоритма 3.6.

Пусть 5={ai, «2.....а„} - множество из п различных элементов, а Т - дерево решений какого-нибудь алгоритма для нахождения k-ro наименьшего элемента в 5. Каждый путь р вТ определяет такое отношение Rp на 5, что aiRpuj, если два различных элемента а; и aj сравниваются в некотором узле, лежащем на р, и в результате этого сравнения либо ai<iaj, либо aiuj ). Пусть RI - транзитивное замыкание отношения Rp). Образно говоря если ai Rl Uj, то последовательность сравнений, представленная путем р, выясняет, что ai<.aj, поскольку никакой элемент не сравнивается сам с собой.

Лемма 3.3. Если на пути р выясняется, что является k-м наименьшим элементом в S, то для любого 1фт, ltn, либо UiR+a, либо aRUi.

Доказательство. Допустим, что некоторый элемент а„ не связан с а„ отношением Покажем, что, поместив а„ либо перед, либо после а„ в линейном порядке, заданном на S, мы получим противоречие с предположением, что путь р правильно установил, что а„ является к-м наименьшим элементом в S. Пусть Si= = {aj\ajRpU}, Si={aj\aaR-laj} и в Ss входят остальные элементы из S. По предположению а„ и а„ принадлежат 5з.

Если Uj- произвольный элемент в Si (соответственно в S2) и а, Rp Uj (соответственно а, i?J а,), то в силу транзитивности а, также принадлежит 5i (соответственно Sg). Следовательно, можно построить такой линейный порядок R, совместимый с что все-элементы множества Si предшествуют всем элементам из s3, кс торые в свою очередь предшествуют всем элементам из S.

По предположению элемент не связан отношением ни с одним элементом из s3. Допустим, что а предшествует а„ при линейном порядке R, т. е. а„ R а„. Тогда можно построить новый линейный порядок R, совпадающий с R во всем, кроме того, что а„ следует непосредственно за а„. Отношение R также совместимо с Rp. Для каждого порядка R и R можно найти различные элементы, удовлетворяющие соответственно R или R. Но а„ не может быть -м наименьшим элементом в обоих случаях, так как в R элементу а„ предшествует на один элемент меньше, чем в R. Г[оэ-тому заключаем, что если какой-то элемент из S не связан с а

Напомним, что мы предполагаем, что каждое сравнение а с b дает результат а<6 или 6<а. В случае ai<.aj сравнивался элемент а,- с а/, в случае ai<.aj сравнивался элемент оу с а,-.

) Транзитивным замыканием отношения R называется такое отношение R + , что cR+d тогда и только тогда, когда существует последовательность истинных утверждений вида ei Rе, «2 Res, ..., em-iRem> где /п2, c=ei н d=e„.



отношением то дерево Т не может правильно выбрать наименьший элемент из S. Случай aRa исследуется аналогично. □

Теорема 3.10. Если Т - дерево решений, выбираюше k-u наименьший элемент в множестве S, S=n, то глубина любого листа дерева Т не меньше п-1.

Доказательство. Рассмотрим путь р в Г из корня к листу. По лемме 3.3 либо а; а„, либо а„ R а; для каждого 1фт, где а„ - элемент, выбранный в качестве k-ro наименьшего. Для элемента а;, {фт, определим ключевое сравнение как первое сравнение на р, содержащее а,- и такое, что выполнено одно из условий:

1) aj сравнивается с а,

2) Ui сравнивается с aj, at RpUj и aj Ra,

3) ai сравнивается с a, а, R at и a„ /?+ a.

Интуитивно ключевое сравнение для - это первое сравнение, из которого можно определить, предшествует элемент элементу а„ или следует за ним.

Понятно, что всякий элемент а,-, кроме а, обладает ключевым сравнением; иначе не выполнилось бы ни at /?J а„, ни а„ R а. Далее, легко видеть, что никакое сравнение не может быть ключевым для обоих сравниваемых элементов. Так как в ключевые сравнения должны вовлекаться п-1 элементов, то длина пути р должна быть не меньше п-1. □

Следствие. Нахождение k-го наименьшего элемента в S требует не меньше п-1 сравнений как в среднем, так и в худшем случае.

На самом деле для всех k, кроме I и п, можно доказать более сильный результат, чем теорема 3.10. (См. упр. 3.21-3.23.)

Если приходится искать алгоритм с хорошим средним временем, который вычисляет fe-й наименьший элемент в S, то подходит стратегия типа той, что применялась в алгоритме Быстрсорт.

Алгоритм 3.7. Нахождение k-го наименьшего элемента

Вход. Последовательность S, состоящая из п элементов произвольного множества с линейным порядком и целое число k.

Выход. &-Й наименьший элемент в S.

Метод. Применяется рекурсивная процедура ВЫБОР, приведенная на рис. 3.12. □

Теорема 3.11. Среднее время работы алгоритма 3.7 линейно.





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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0038