§ 17. Нижняя граница сложности в среднем

123

получаются перестановками элементов массива х₁,х₂,...,х_п и при этом сравнения элементов с теми же самыми индексами, которые использовались в уже произведенных сравнениях элементов массива х₁,х₂, ...,х_п, дают для массивов из М результаты, совпадающие с по­лученными для х₁, х₂,...,х_п. Представим множество М в виде объеди­нения двух непересекающихся подмножеств М₁ и М₂, где в М₁ вхо­дят те массивы, для которых у <у_;-, а в М₂—те, для которых у,- <у. Покажем, что в М₁ больше элементов, чем в М₂. Операция обмена у <—>у_;- определяет взаимно однозначное отображение на себя мно­жества всех массивов, которые получаются перестановками элемен­тов массива х₁,х₂, ...,х_п. Обратным к этому отображению является оно само. В силу определения множеств В и С это отображение пе­реводит элементы множества М₁ в элементы множества М₂. Следова­тельно, в М₁ элементов не больше, чем в М₂. Но в М₂ найдется мас­сив, который при этом отображении не переходит в массив из М₁ и, более того, вообще покидает множество М (чтобы убедиться в этом, достаточно заметить, что в М₂ имеется такой массив У₁,у₂, ...,у_п, для которого yj = тт{у₁,у₂, ...,у„}). Поэтому в М₁ элементов меньше, чем в М₂. Если т₁, т₂ обозначают количества элементов множеств М₁ и М₂, то имеем

— < —

т₁+т₂ т₁ + т₂

и, следовательно,

m1 1

— < .

т₁+т₂ 2

Таким образом, вероятность того, что i-й элемент меньше j-го, есть ¹₂ - е, е > 0. Получаем

ЕД1 = -2¹₂ - е) = -1 + 2е > -1.

Тип АВ. Аналогично предыдущему можно показать, что при лю­бом способе выбора индексов таких, что х_{ е А, х_;- е В, вероятность

выполнения неравенства x_t > х_;- есть - - е, е > 0. Получаем

ЕД1 = -!(¹₂-е) -1(1+_е)=-1 + е>-1.

Тип АС. Рассматривается аналогично типу АВ.

В дальнейшем будет полезна оценка е для сравнений типов АВ и АС. Рассмотрим для определенности АВ. Очевидно, что чем больше сравнений к рассматриваемому моменту прошел элемент х_;- е В, тем меньше вероятность того, что элемент x_teA окажется больше него.

124 Глава 4. Нижняя граница сложности. Оптимальные алгоритмы

Наибольшая же вероятность получится в случае, когда х_;- сравнивал­ся только с одним элементом, например с x_s, и x_s—это наименьший элемент исходного массива. Вычислим вероятность, с которой в этом случае x_t>Xj. Итак, если упорядочить все элементы, кроме x,Xj, то x_s окажется наименьшим (первым). Общее число способов, которыми к этой упорядоченной совокупности можно добавить x,Xj, с учетом x_s < xj равно n(n - 2) (для добавления _Xj существует п - 2 способа, за­тем добавляем x, и для этого существует п способов). Из них ₂) - 1 соответствуют неравенству x_t < x_i (возможен любой выбор двух среди п мест, кроме двух первых). Интересующая нас вероятность равна

п(п-2)-(^п) + 1 1 1

■ ■

п(п-2) 2 2п

Это дает нам е ^ 1-, и, таким образом,

для АВ и АС. Если при четном п удастся обойтись сравнениями ти­пов АА,ВВ,СС, то сравнений потребуется в точности ³₂п-2. Если п нечетно, то для решения задачи обязательно потребуется произве­сти хотя бы одно сравнение типа АВ, АС или AD. Сравнение типа AD

дает Д1 = -¹₂>-1 + ₂¹ .

Можно убедиться и в том, что для сравнений типов АВ и АС выполняется ЕД1^-1 + —, если ЕД1 рассматривается как матема­тическое ожидание при условии, что значения Д1 для всех преды­дущих сравнений, предписываемых алгоритмом, известны. Эти из­вестные значения определяют некоторое событие V в вероятност­ном пространстве П„. Событие V может быть представлено как сум­ма V₁ + V₂ + ... + V_l попарно несовместных событий, где каждое V_k состоит из тех элементов П„, для которых все предыдущие сравне­ния образуют некоторую фиксированную последовательность срав­нений элементов с вполне определенными для данного к индекса­ми, и при этом возникающие значения Д1 совпадают с известными

из условия. В силу доказанного выше E(AL|V_fc) ^ -1 + ₂- для каж­ дого к ^ Z. Отсюда по формуле полного математического ожидания E(AL|V)^ ¹

2п

-1 +

В сумме 2 ^пк, о которой идет речь в теореме 17.1, мы можем поло-fc=1 жить h_k = 1 для всех значений к, кроме какого-то одного значения к₀,