Главная » Java, Структуры данных и алгоритмы » Рандомизированная быстрая сортировка

0

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

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

Утверждение 10.5. Предполагаемое время выполнения рандомизированной быстрой сортировки последовательности размером п составляет 0(п log п).

Доказательство. Воспользуемся простым фактов теории вероятности.

Чтобы монета упала «орлом» к раз, ее следует подбросить 2к раз.

Рассмотрим теперь один шаг рекурсии рандомизированной быстрой сортировки, где т — размер исходной последовательности данного вызова. Вполне достаточно, если выбранная точка отсчета поделит последовательность на L, равную т/4, и G, равную Зт/4. Таким образом, поскольку точка отсчета выбирается случайно, имеем т/2 точек отсчета, которые удовлетворяют условию, то есть вероятность удачного выбора составляет 1/2 (как и в случае с монетой).

Если узел v дерева Г, как показано на рис. 10.14, соответствует удачному рекурсивному выбору, то исходный размер дочерних элементов узла v составит максимум 3s(v)/4 (что можно записать как s(v)/(4/3)). Длина любого маршрута из корня Т к простому узлу будет равна количеству вызовов, которые нужно сделать (в каждом узле на этом маршруте) до полу-

Рис. 10.14. Отображение времени выполнения дерева быстрой сортировки Т

чения log4/3п удачных вызовов. При использовании вероятностного фактора необходимое количество вызовов должно составить 2 log 4/3 п. Таким образом, предполагаемая длина любого маршрута от корня до простого узла в дереве Г есть 0(log п). Поскольку время, расходуемое на каждом уровне Г, есть 0(п), предполагаемое время выполнения рандомизированной быстрой сортировки составит 0(п log п).

В принципе применение вероятностных факторов позволяет доказать, что время выполнения рандомизированной быстрой сортировки составляет 0(п log п) с высокой степенью вероятности. Читатели, склонные к математике, могут произвести этот анализ, выполнив упражнение 3-10.7.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии