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

121

инверсионного вектора перестановки. Эта функция является случай­ной величиной на П_n, при этом ДL = -1 на каждом шаге алгоритма. В других ситуациях начальное значение L может определяться одно­значно, тогда как ДL является случайной величиной. Сформулируем теорему, полезную в этих ситуациях.

Теорема 17.1. Пусть £₁,£₂, ... —последовательность неотрица­тельных случайных величин на некотором вероятностном простран­стве. Пусть числовая последовательность h₁,h₂, ... такова, что для каждого k^1 выполнено E(C_kl^1, ?₂, ..., ?k-1) ** h при всех значениях ?₁, ?2, ..., S_k-1. Зафиксируем неотрицательное число q и введем цело­численную случайную величину

т = minn:

7 Л

k=1

Пусть т < оо всюду на рассматриваемом вероятностном простран­стве. Тогда е( £ h_k ^ q.

k=1

Доказательство приведено в приложении E.

Для того чтобы воспользоваться этой теоремой, можно опять по­пытаться определить некоторую неотрицательную функцию L, отра­жающую степень «недорешенности» рассматриваемой задачи: значе­ние L равно нулю, если алгоритм доработал до конца и задача ре­шена. Считаем, что всем входам фиксированного размера сопостав­ляется одно и то же значение функции L. После выбора такой функ­ции L мы должны показать, что последовательность величин Е(-ДL), соответствующих идущим друг за другом этапам алгоритма, огра­ничена сверху некоторой известной числовой последовательностью h₁,h2, ...; тогда случайная величина т, равная для данного входа об­щему количеству этапов, приводящих к завершению алгоритма, та­кова, что Е( 2 hk ) ^ q, где q — значение функции L, сопоставляе-

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

Пример 17.2. Вернемся к задаче одновременного выбора наиболь­шего и наименьшего элементов массива длины n, n ^ 2, с помощью сравнений (пример 15.1). Вероятностным пространством здесь вновь будем считать П_n. Каждая перестановка из П_n отражает, как обычно,

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

взаимный порядок элементов исходного массива. Все перестановки считаются равновероятными.

Чтобы воспользоваться теоремой 17.1, мы полагаем, что случай­ные величины Е,₁, Е,₂, ... для произвольного алгоритма одновременно­го выбора наибольшего и наименьшего элементов равны значениям -AL на последовательных шагах этого алгоритма, об определении функции L будет сказано ниже. Значения £₁,£₂, ... зависят от кон­кретной перестановки из П_n, отражающей взаимный порядок элемен­тов в исходном массиве. После того, как алгоритм закончил работу, значения Е,_k при последующих значениях k равны нулю.

Предложение 17.2. Функция

(-n - 2, если n четно,

3 1 (17.1)

I 2n - 2 + _{2 n}-, если n нечетно,

является нижней границей сложности в среднем алгоритмов одновре­менного выбора наибольшего и наименьшего элементов массива дли­ны n, n ^ 2, c помощью сравнений.

Доказательство. Вновь обратимся к множествам A, B, C, D, к рас­смотренным в доказательстве предложения 15.1 типам AA,AB, ...,DD сравнений, количествам a, b, c, d элементов множеств A, B,C,Dи функ­ции L(a, b, c, d) = ³₂a + b + c - 2 (равенство L = 0 является необходимым и достаточным условием того, что искомые элементы найдены).

Пусть в процессе выбора наибольшего и наименьшего элементов массива уже произведены некоторые сравнения элементов этого мас­сива. При каждом из этих сравнений получался некоторый результат «истина» или «ложь», и эти результаты нам известны. Если процесс выбора наибольшего и наименьшего элементов еще не завершен, то следующим шагом вновь будет некоторое сравнение одного из типов AA, AB,..., DD. Сравнения AB, AC и BC представляют особый интерес, так как можно бы предположить, что здесь получится ЕДL<-1. Но на самом деле это неравенство не имеет места ни при одном из этих трех типов сравнений.

Тип BC. Покажем невозможность такого выбора индексов i и j, основанного только на результатах уже произведенных сравнений, что x_i g B, xj g C и при этом с вероятностью, не меньшей половины, выполняется x_i < x_j.

Пусть сделан некий выбор индексов i и j, при котором x_i е B, xj g C. Рассмотрим множество M всех массивов y ₁,y₂, ...,y_n, которые