§ 8. Функция затрат рандомизированного алгоритма

63

Итак,

п-1

Ег = п - 1 + - У Er_k, Ег₀ = 0.

fc=0

Такого вида соотношения уже встречались в предыдущем параграфе, и по аналогии с (7.1) мы находим

Е_Хп = 2п In п + 0{п). (8.3)

Возвратимся к рандомизированной быстрой сортировке. Для дан­ного массива длины п математическое ожидание затрат, измеряемых числом сравнений, полностью определяется значением п. Поэтому, например, сложность в худшем случае, т. е. максимум математиче­ских ожиданий рассматриваемого вида для массивов длины п, есть просто математическое ожидание, найденное при рассмотрении это­го п. Мы можем переписать (8.3) как соотношение для сложности f_QS(n) по числу сравнений рандомизированной быстрой сортировки:

f_QS(n) = 2n In п + 0(п).

Вновь можно заметить, что число перемещений, требуемое ран­домизированной быстрой сортировкой для конкретного массива, не превосходит числа сравнений, домноженного на некоторую констан­ту, откуда сложность в среднем Т' (п) по числу перемещений эле­ментов допускает оценку 7^_s(n) = 0{п log п). Как и обычная быстрая сортировка, рандомизированная быстрая сортировка не использует дополнительных массивов, поэтому Sg_S(n) = 0(l).

Сложность рандомизированной быстрой сортировки как по числу сравнений, так и по числу перемещений элементов допускает оцен­ку 0(n log п). Пространственная сложность по числу одновременно хранимых дополнительных величин, равных каким-то элементам ис­ходного массива, допускает оценку 0(1).

При использовании принципа «из двух заданий первым выполня­ется более простое», мы получаем, согласно теореме 7.1, для сложно­сти по объему стековой памяти оценкуJog₂ п.

Совпадению сложностей f_QS(n) и T_QS(n) можно дать объясне­ние: случайный выбор разбивающего элемента, предпринимаемый на каждом этапе сортировки, эквивалентен тому, что мы меняем порядок исходного массива случайным образом и затем применяем «обычную» быструю сортировку; но равенство сложностей такого ро­да не обязано иметь место для других алгоритмов, — все-таки речь идет о математических ожиданиях случайных величин, определенных

64

Глава 2. Сложность в среднем

на разных вероятностных пространствах. Например, можно несколь­ко ускорить рандомизированную быструю сортировку, если разбива­ющий элемент определять путем случайного выбора без возвращения трех элементов массива и последующего определения второго по ве­личине из этих трех; можно показать, что тогда вместо 2n In n + O{n)

возникнет у n In n + O{n) , и совпадения сложностей обычной и ран­домизированной быстрой сортировки уже не будет.

Возвращаясь к примеру 3.1, мы видим, что, основываясь на ран­домизированной быстрой сортировке, можно получить алгоритм по­строения выпуклой оболочки данных n точек координатной плоскости, имеющий сложность в среднем O{n log n) по общему числу операций.

При нахождении или оценивании сложности какого-либо рандоми­зированного алгоритма часто не возникает необходимости детального рассмотрения всевозможных сценариев. Бывает достаточно рассмот­реть сходное с (8.2) разложение пространства сценариев и применить формулу полного математического ожидания. Даже если множество всех сценариев бесконечно, разложение вида (8.2) можно выбрать ко­нечным.

Пример 8.2. Массив x_ъx₂,...,x_n назовем массивом, содержащим большинство, если больше половины его элементов имеют равные значения. Пусть над элементами массивов разрешена операция про­верки равенства двух элементов, будем называть эту операцию срав­нением. Пусть для данного массива, содержащего большинство, тре­буется найти i, l^i^n, такое, что значение x_i принадлежит боль­шинству значений элементов x₁,x₂,...,x_n. Один из возможных ран­домизированных алгоритмов решения этой задачи состоит в том, что i выбирается случайно (распределение вероятностей равномер­но), а затем проверяется, удовлетворяет ли x_i поставленному усло­вию, — сравнений на эту проверку уйдет не более n- 1. Если x_i не подходит, то все повторяется. Сложность в среднем по числу срав­нений этого алгоритма не превосходит 2(n- 1). В самом деле, про­странство всех сценариев разлагается на два события: первая попыт­ка найти нужное i оказывается удачной и, соответственно, эта по­пытка оказывается неудачной. По формуле полного математического ожидания имеем для искомого среднего a:

a^p(n-1) + (1-p)(a + n-1).

Отсюда a^-(n-1)<2(n-1). p

Доказательство имеется, например, в [59, разд. 3.7].

Задачи

65

Еще один путь получения этого же результата. Так как вероят­ность p удачного выбора индекса i больше половины, то математи­ческое ожидание количества попыток, которые потребуются для полу­чения удачного значения i, меньше двух. Отсюда среднее число срав­нений a меньше, чем 2(n - 1).

Теоретически нет никакого препятствия к тому, чтобы при опре­делении функции затрат рандомизированного алгоритма взять вме­сто математического ожидания максимум затрат по соответству­ющим сценариям (при таком подходе рандомизированная быст­рая сортировка имеет квадратичную сложность). Но обычно для рандомизированных алгоритмов рассматриваются усредненные зат­раты.

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

Мы вернемся к этому в § 18.

Задачи

23. Верно ли, что для рассмотрения сложности в среднем некото­ рого алгоритма требуется задание распределения вероятностей

а) на множестве всех допустимых входов?

б) на каждом из множеств всех входов фиксированного размера?

24. Как говорилось при обсуждении асимптотического закона рас­ пределения простых чисел, в [39] приводится элементарное доказа­ тельство неравенств Чебышева с C = 6, c = 1/3. Добавим, что наибо­ лее легко доказывается нижняя оценка

π(n)> -—,

справедливая для всех n > 1. Доказать, что сложность в среднем алго­ритма пробных делений не является полиномиально ограниченной, используя для этого только последнее неравенство и не прибегая к полному варианту асимптотического закона распределения простых чисел.

См., например, [55].

66