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

В АН], то, рассуждая, как и выше, можно показать, что после вызова процедуры ПЕРЕСЫПКА(1, п) все узлы i, . . ., п будут корнями сортирующих деревьев. □

Теорема 3.5. Алгоритм 3.3 преобразует А в сортирующее дерево за линейное время.

Доказательство. Применяя лемму 3.2, можно с помощью простой возвратной индукции по i показать, что узел i становится корнем какого-нибудь сортирующего дерева для всех i.

Пусть Т [К) - время выполнения процедуры ПЕРЕСЫПКА на узле высоты h. Тогда Т {h)T (h-для некоторой постоянной с. Отсюда вытекает, что Тф.) есть 0(h).

Алгоритм 3.3 вызывает процедуру ПЕРЕСЫПКА, если не считать рекурсивных вызовов, один раз для каждого узла. Поэтому время, затрачиваемое на ПОСТРСОРТДЕРЕВА, имеет тот же порядок, что и сумма высот всех узлов. Но узлов высоты i не больше, чем Г п/2+»"]. Следовательно, общее время, затрачиваемое процедурой ПОСТРСОРТДЕРЕВА, имеет порядокin/2, т. е. О (п). □

Теперь можно завершить детальное описание алгоритма СОРТ-ДЕРЕВОМ. Коль скоро элементы массива А преобразованы в сортирующее дерево, некоторые элементы удаляются из корня по одному за раз. Это делается перестановкой All] и А[п] и последующим преобразованием All], А[2]..... Л[п-1] в сортирующее

дерево. Затем переставляются All] и А1п-1], а All], А12], . . . .. ., Aln-2] преобразуется в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда All], А12], . . ., Л[п] - упорядоченная последовательность.

Алгоритм 3.4. Сортдеревом

Вход. Массив элементов АН], l<t<n.

Выход. Элементы массива Л, расположенные в порядке неубывания.

Метод. Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм 3.3. Наш алгоритм выглядит так: begin

ПОСТРСОРТДЕРЕВА; fort-n step -1 until 2 do begin

переставить Л[1] и A[i]; ПЕРЕСЫПКА(1, t-1)

end □



Теорема 3.6. Алгоритм 3.4 упорядочивает последовательность из п элементов за время 0{п log п).

Доказательство. Корректность алгоритма доказывается индукцией по числу выполнений основного цикла, которое обозначим через т. Предположение индукции состоит в том, что после т итераций список А[п-т+1]..... А[п] содержит т наибольших элементов, расположенных в порядке неубывания, а список Л[1],. . ., А[п-т] образует сортирующее дерево. Детали доказательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, г) есть O(logt)- Следовательно, алгоритм 3.4 имеет сложность 0(п log п). □

Следствие. Алгоритм Сортдеревом имеет временную сложность Ос{п log п).

3.5. БЫСТРСОРТ - УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ O(nlogn)

До сих пор мы рассматривали поведение сортирующих алгоритмов только в худшем случае. Для многих приложений более реалистичной мерой временной сложности является усредненное время работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь среднюю временную сложность, существенно меньшую п log п. Однако известны алгоритмы сортировки, которые работают в худшем случае сп времени, где с - некоторая постоянная, но среднее время работы которых относит их к лучшим алгоритмам сортировки. Примером такого алгоритма служит алгоритм Быстрсорт, рассматриваемый в этом разделе.

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

Общий метод состоит в том, чтобы поставить в соответствие каждому листу V дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям. Таким образом, можно определить среднее число сравнений, производимых данным алгоритмом сортировки, если вычислить сумму pidf,

взятую по всем листьям дерева решений данного алгоритма, в которой Pi- вероятность достижения t-ro листа, а di- его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4.



Теорема 3.7. В предположении, что все перестановки п-эле-ментной последовательности появляются на входе с равными вероятностями, любое дерево решений, упорядочивающее последовательность из п элементов, имеет среднюю глубину не менее log п\.

Доказательство. Обозначим через D(Т) сумму глубин листьев двоичного дерева Т. Пусть D (Т) - ее наименьшее значение, взятое по всем двоичным деревьям Т cm листьями. Покажем индукцией по т, что D {т)т log т.

Базис, т. е. случай т=1, тривиален. Допустим, что предположение индукции верно для всех значений т, меньших k. Рассмотрим дерево решений Тек листьями. Оно состоит из корня с левым поддеревом Ti с i листьями и правым поддеревом Tk-t с k-i листьями при некотором I, 1<1<А. Ясно, что

DiT) = i+D (Т,.) -f (/г - О + D (r, i). Поэтому наименьшее значение D (Т) дается равенством

D(k)= mN[k-\-D(i)-}-D(k-i)]. (3.1)

\<i<k

Учитывая предположение индукции, получаем отсюда

D{k)k + MIN [i logi + {k- i) log(k - i)]. (3.2)

i<i<k

Легко показать, что этот минимум достигается при i=kl2. Следовательно,

D(k)k-\-k\og\ = k\ogk.

Таким образом, D(m)m log т для всех т>1.

Теперь мы утверждаем, что дерево решений Т, упорядочивающее п случайных элементов, имеет не меньше п1 листьев. Более того, в точности п\ листьев появляются с вероятностью 1/п! каждый, а остальные - с вероятностью 0. Не изменяя средней глубины дерева Т можно удалить из него все узлы, которые являются предками только листьев вероятности 0. Тогда останется дерево Т с п! листьями, каждый из которых достигается с вероятностью 1/п!. Так как D(7")>nl log п!, то средняя глубина дерева Т (а значит, и Т) не меньше (1/п!) п! log n! = log n!. □

Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп log п сравнений для некоторой постоянной с>0.

Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сп log п для некоторой постоянной с (как и у всякой сортировки с помощью сравнений), но составляет лишь часть





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