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

мента. Например, из рис. 8.1 видно, что элемент 1 является элементом глубины 3, а элемент 6 - глубины 5.

Чтобы реализовать самый худший случай выполнения процедуры quicksort, мы должны управлять выбором опорного элемента, например выбрать в качестве опорного значения наибольшее значение ключа в сортируемом множестве элементов. Тогда сортируемое множество элементов разбивается на два подмножества, одно из которых содержит только один элемент (ключевое значение этого элемента совпадает с опорным значением). Такая последовательность разбиения исходного множества приводит к структуре дерева, подобного изображенному на рис. 8.3, где записи г, Г2 г„ заранее упорядочены в порядке возрастания ключей.

В приведенном примере элемент rf (2 < i < п) имеет глубину п - i - 1, а глубина элемента составляет л - 1. Сумма глубин


г элементов равна

Рис. 8.3. Наихуд- „ i + у , + 1, = 1,

шол возможная по- ~ 2 2

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

Время выполнения быстрой сортировки в среднем

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

Сделаем еше одно предположение, которое тоже упрошает анализ. Будем считать, что при вызове процедуры quicksort(i, j) все упорядочивания элементов A[i), A\j] равновероятны. Это предположение можно попытаться обосновать исходя из того очевидного факта, что опорное значение v, примененное в предыдушем вызове quicksort, нельзя использовать для разбиения данного подмножества элементов, так как здесь все элементы имеют значения ключей либо меньшие v, либо большие, либо равные v. Более тшательный анализ программы быстрой Сортировки показывает, что предыдуший опорный элемент скорее всего будет находиться возле правого конца подмножества элементов, равных или больших этого опорного значения (т.е. не будет находиться с равной вероятностью в любом месте этого подмножества), но для больших множеств этот факт не имеет определяюшего значения.

Обозначим через Т(п) среднее время, затрачиваемое алгоритмом быстрой сортировки на упорядочивание последовательности из и элементов. Очевидно, что время Т( 1) равно некоторой константе с, поскольку имеется только один элемент и не ис-

Конечно, порядок элементов >4(i]. A\J\ будет зависеть от первоначального упорядочивания элементов А\п\ и от ранее выбранньк опорных элементов (см. в тексте следующее предложение и следующий абзац). Но основываясь на предположении о равных вероятностях всех упорядочений исходной последовательности элементов и на том факте, что предыдущее опорное значение влияет на количество и состав элементов .4 /. . . . A[j\, но мало влияет на их взаимное расположение, в первом приближении гипотеза о равновероятности всех упорядочений элементов j4[i], выглядит вполне приемлемой. - Прим. ред.

Из приведенных рассуждений можно сделать практический вывод: если сортировка выполняется не так быстро, как ожидалась, то можно предварительно переупорядочить сортируемые элементы в случайном порядке, а затем повторить быструю сортировку.



пользуется рекурсивный вызов процедуры quicksort самой себя. При и > 1 требуется время сп (сг - некоторая константа), чтобы определить опорное значение и разбить исходное множество элементов на два подмножества; после этого вызывается процедура quicksort для каждого из этих подмножеств. Было бы хорошо (с точки зрения анализа алгоритма), если бы мы могли утверждать, что для подмножества, которое упорядочивается данным вызовом процедуры quicksort, опорное значение с одинаковой вероятностью может быть равным любому из п элементов исходного множества. Но в этом случае мы не можем гарантировать, что такое опорное значение сможет разбить это подмножества на два других непустых подмножества, одно из которых содержало бы элементы, меньшие этого опорного значения, а другое - равные или большие его. Другими словами, в рассматриваемом подмножестве с ненулевой вероятностью могут находиться только элементы, меньшие этого опорного значения, либо, наоборот, большие или равные опорному значению. Именно по этой причине в алгоритме быстрой сортировки опорное значение выбирается как наибольшее значение ключей первых двух различных элементов. Отметим, что такое определение опорного значения не приводит к эффективному (т.е. примерно равному) размеру подмножеств, на которые разобьется рассматриваемое подмножество относительно этого опорного значения. При таком выборе опорного значения можно заметить тенденцию, что "левое" подмножество, состояшее из элементов, чьи ключи меньше опорного значения, будет больше "правого" подмножества, состояшего из элементов, ключи которых больше или равны опорному значению.

Предполагая, что все сортируемые элементы различны, найдем вероятность того, что "левое" подмножество будет содержать i из и элементов. Для того чтобы "левое" подмножество содержало i элементов, необходимо, чтобы опорное значение совпадало с (i -Ь 1)-м порядковым значением в последовательности упорядоченных в возрас-таюшем порядке элементов исходного множества. При нашем методе выбора опорного значения данное значение можно получить в двух случаях: (1) если элемент со значением ключа, равного (i + 1)-му порядковому значению, стоит в первой позиции, во второй позиции стоит любой из i элементов с ключами, меньшими, чем у первого элемента; (2) элемент со значением ключа, равного новому опорному значению, стоит на второй позиции, а в пфвой - любой из i элементов с ключами, меньшими чем у второго элемента. Вероятность того, что отдельный элемент, такой как (i + 1)-е порядковое значение, появится в первой позиции, равна Вероятность того, что во второй позиции будет стоять любой из / элементов со значением ключа, меньшим, чем у первого элемента, равна i/(n- 1). Поэтому вероятность того, что новое опорное значение находится в первой позиции, равна 1/п(п- 1). Такое же значение имеет вероятность события, что новое опорное значение появится во второй позиции. Отсюда вытекает, что "левое" множество будет иметь размер / с вероятность 2i/n(n- 1) для 1 < i < п.

Теперь можно записать рекуррентное соотношение для Г(ге):

Т(п)<% [тут Т(п-i)] сп. (8.1)

Неравенство (8.1) показывает, что среднее время выполнения алгоритма быстрой сортировки не превышает времени сгп, прошедшего от начала алгоритма до рекурсивных вызовов quicksort, плюс среднее время этих рекурсивных вызовов. Последнее время является суммой по всем возможным i произведений вероятностей того, что "левое" множество состоит из i элементов (или, что то же самое, вероятностей того, что "правое" множество состоит из я - / элементов) и времени рекурсивных вызовов T(i) и Т(п - i).

Теперь надо упростить сумму в выражении (8.1). Сначала заметим, что для любой функции f{i) путем замены i на. п - i можно доказать следующее равенство:

Х№) = Х/(п-0- (8.2)

1=1 i-i

Из равенства (8.2) следует, что



S/W = ;i;C/(0 + /(ra-t)).

il (=1

(8.3)

Положив f(i) равными слагаемым в выражении (8.1) и применяя равенство (8.3), из неравенства (8.1) получим

"(1 - 1)

{ТЦ) + Пп-()] + с,п.

(8.4)

Далее снова применяем формулу (8.3) к последней сумме в (8.4), положив

т - nty.

Пп)<-УГ(() + с,п.

1 -i"

(8.5)

(Отметим, что последнее неравенство в (8.4) соответствует выражению, которое мы получили бы, если бы предполагали равные вероятности для всех размеров (от 1 до п) "левых" множеств.) Решение рекуррентных соотношений мы подробно рассмотрим в главе 9. Здесь мы покажем, как можно оценить сверху решение рекуррентного неравенства (8.5). Мы докажем, что для всех и 2 Т{п)< сп logra для некоторой константы с.

Доказательство проведем методом индукции по п. Для п = 2 непосредственно из неравенства (8.5) для некоторой константы с получаем Т(2) < 2с - 2с log2. Далее, в соответствии с методом математической индукции, предположим, что для i < я выполняются неравенства T(i) < ci logi. Подставив эти неравенства в формулу (8.5), для Т{п) получим

T{n)<"ilogH-c,n. п -1 „1

(8.6)

Разобьем сумму в (8.6) на две суммы: в первой / < п/2, во второй / > п/2. В первой сумме log i < log(n/2) = log л - 1, во второй сумме log / не превышают log п. Таким образом, из (8.6) получаем

Г(п)<

п -1

У, i(log re -1) -i- г log л

+ с,ге <

~(- l)log л --(-+ 1) - -71(- - l)log rt

4- с,ге =

2 2 .8 4

ГЦ т < СП log П---+ С,П.

4 2(ге-1)

(8.7)

Если положить с > 4с2, тогда в последнем выражении сумма второго и четвертого слагаемых не превысит нуля. Третье слагаемое в последней сумме (8.7) отрицательное, поэтому можно утверждать, что Т(п)< сп logn для константы с = 4с2. Этим заканчивается доказательство того, среднее время выполнения алгоритма быстрой сортировки составляет 0(ге logre).





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