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

procedure BbIBOP(fe, S):

1. if ISI = 1 then return единственный элемент множества S else

begin

2. случайно выбрать элемент a из S;

3. пусть Sj, Sj и Sg - последовательности элементов из S,

меньших, равных и больших а соответственно;

4. if Sj>fe then return ВЫБОР(/г, S) else

5. if ISJ + JSalfe then return a

6. else return BbIBOP(fe-Si -SJ, S,) end

Рис. 3.12. Алгоритм выбора.

Доказательство. Пусть Т{п) - среднее время работы процедуры ВЫБОР на последовательности из п элементов. Предположим для простоты, что все элементы множества S различны. (При наличии повторяющихся элементов результат не изменится.)

Пусть элемента, выбранный в строке 2, является i-м наименьшим элементом в S. Число i может принимать значения 1, 2, . . ., п равновероятно. Если i>k, то ВЫБОР вызывается для последовательности, состоящей из i-1 элементов, а если Kk, то для последовательности, состоящей из n-i элементов. Поэтому среднее время работы рекурсии в строке 4 или 6 равно

i=k+\

Остальная часть процедуры ВЫБОР занимает время сп для некоторой постоянной с, так что при п>2

Г(пХсп+МАХ

п-1 л-1

(3.9)

В качестве упражнения на индукцию предлагаем доказать, что если Г(1Хс, то Т{п)4сп для всех п>2. □

УПРАЖНЕНИЯ

3.1. Примените алгоритм 3.1 для упорядочения последовательности цепочек abc, acb, bca, bbc, асе, bac, baa.




Рис. 3.13. Два дерева.

3.2. Примените алгоритм 3.2 для упорядочения последовательности цепочек а, be, aab, baca, cbc, cc.

3.3. Проверьте, изоморфны ли два дерева на рис. 3.13 в смысле примера 3.2.

3.4. Упорядочите список 3, 1,4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9 7, применяя (а) Сортдеревом, (б) Быстрсорт, (в) Сортслиянием (алгоритм 2.4). Сколько сравнений производится в каждом случае?

3.5. Рассмотрите следующий алгоритм, упорядочивающий последовательность элементов ai, fla, . . ., On, хранящихся в массиве Л, т. е. A{i\=ai для lin:

procedure СОРТВЗБАЛТЫВАНИЕМ(Л): for j = n-\ step -1 until 1 do for 1 = 1 step 1 until / do

if Л [t + 1] < Л [i] then переставить Л [i] и Л [i + 1]

(а) Докажите, что СОРТВЗБАЛТЫВАНИЕМ располагает элементы в Л в порядке неубывания.

(б) Определите время работы СОРТВЗБАЛТЫВАНИЕМ в худшем случае и в среднем.

3.6. Закончите доказательство того, что сортирующее дерево можно построить за линейное время (теорема 3.5).

3.7. Закончите доказательство того, что Сортдеревом требует время 0{п log га) (теорема 3.6).

3.8. Покажите, что время работы Быстрсорт в худшем случае есть О(п).

3.9. Каково время работы в худшем случае у алгоритма 3.7, находящего k-K наименьший элемент?



*3.10. Докажите, что среднее время упорядочения последовательности из п элементов ограничено снизу величиной сп log п для некоторой постоянной с, закончив доказательство теоремы 3.7 и решив уравнение (3.2).

3.11. Закончите доказательство того, что алгоритм 3.6 находит й-й наименьший элемент за время 0{п) (теорема 3.9), решив уравнение (3.8).

*3.12. Докажите корректность подпрограммы разбиения, приведенной на рис. 3.8, и проанализируйте время ее работы.

3.13. Закончите доказательство того, что алгоритм 3.7 для нахождения fe-ro наименьшего элемента работает в среднем 0(п) времени (теорема 3.11), решив уравнение (3.9).

*3.14. Покажите, что среднее число сравнений, требуемых алгоритмом 3.7, не превосходят 4п. Можете ли вы улучшить эту оценку, если известно значение k, при котором будет применяться алгоритм?

*3.15. Пусть S - последовательность элементов, содержащая т,- экземпляров 1-го элемента для l<i<&. Пусть п= Докажите, что

Q(" + °gmi!m/...m,l)

сравнений необходимо и достаточно, чтобы упорядочить S.

3.16. Пусть Si, Si, . . ., Sft-множества чисел, лежащих между 1 и п, и сумма мощностей всех Si равна п. Опишите алгоритм сложности 0{п), упорядочивающий все Sj.

3.17. Пусть даны последовательность а, аг, . . ., а„ и перестановка я(1), л(2), . . ., п{п). Напишите алгоритм на Упрощенном Алголе, который располагал бы эту последовательность в порядке ж!). Ол(2) . • •, йя(п). работая на том же месте, где она записана вначале. Каково время работы вашего алгоритма в худшем случае и в среднем?

*3.18. В процессе построения сортирующего дерева размера 2*-1 мы строим два сортирующих дерева размера 2*"-1, затем соединяем их, добавляя корень и проталкивая элемент, стоящий в корне, вниз на его надлежащее место. Столь же легко можно было бы построить сортирующее дерево, добавляя за один шаг один элемент в качестве листа и проталкивая этот новый элемент вверх по дереву. Напишите алгоритм, который строил бы сортирующее дерево с помощью добавления листа (одного на каждом шаге), и сравните порядок сложности вашего алгоритма и алгоритма 3.3.





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.0024