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

59

зависят от сценария вычисления. При фиксированном входе мы мо­жем рассмотреть множество всех сценариев и, приписав адекватным образом каждому из сценариев некоторую вероятность, ввести на по­лученном вероятностном пространстве случайную величину, значе­ние которой для данного сценария равно соответствующим вычисли­тельным затратам. Значение функции затрат на данном входе можно положить равным математическому ожиданию этой случайной вели­чины (усредненным затратам для данного входа). А после того как определена функция затрат и принято соглашение о том, что такое размер входа, мы можем, как обычно, рассматривать сложность ал­горитма— в худшем случае или же в среднем (последнее возможно, если только множество входов каждого фиксированного размера яв­ляется вероятностным пространством).

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

Пример 8.1. Вновь обратимся к быстрой сортировке. В § 7 на­ми установлено, что быстрая сортировка имеет сравнительно низкую сложность в среднем в предположении, что для каждого п > О все от­носительные порядки элементов входных массивов длины п имеют

одинаковую вероятность —. Но в некоторых практических задачах это предположение может оказаться безосновательным в силу того, что все входные массивы изначально оказываются, например, «почти упорядоченными». Число сравнений, затрачиваемых быстрой сорти­ровкой на каждом таком «почти упорядоченном» массиве, будет близ­ко к п², что сведет на нет достоинства быстрой сортировки.

Однако если разбивающий элемент выбирать случайно, то при каждом фиксированном входе размера п усредненные затраты будут иметь порядок n log п, что и будет показано ниже. Итак, под ран­домизированной быстрой сортировкой мы будем понимать быструю сортировку со случайным выбором индекса разбивающего элемента; если надо выбрать случайное значение т из fc,fc + l,...,?, то мы по­лагаем т := k + randomQ. - к + 1). В том алгоритме, который записан в виде процедуры в конце § 7, вместо

х_к выбирается в качестве разбивающего элемента и выполняет­ся разбиение х_к,х_к+ъ ...,х₁; пусть i—индекс, получаемый раз­бивающим элементом после разбиения;

60

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

можно написать

m :=fc + random(Z-fc + 1);

x_m выбирается в качестве разбивающего элемента и выпол­няется разбиение х_к,х_к+1, ...,х_;; пусть i — индекс, получаемый разбивающим элементом после разбиения;

это даст рандомизированный вариант быстрой сортировки.

Пусть дан массив х₁, х₂,...,х_п попарно различных чисел. Пусть мы выбираем элемент т из множества {1,2, ...,п} и вероятность выбора

каждого из элементов есть -. Тогда место х_т в массиве х₁,х₂,...,х_п после сортировки этого массива может оказаться любым с одной и той же вероятностью -. В самом деле, пусть К^пи пусть l(i) та-ково, что Х₍) занимает после сортировки массива место с номером i. Это Z(i) определяется единственным образом. Поэтому вероятность попадания х_т после сортировки массива на i-е место равна вероят­ности того, что m = Z(i). Последняя вероятность, очевидно, равна -.

_п

Следовательно, приписывание одинаковой вероятности каждому воз­можному выбору индекса разбивающего элемента ведет к тому, что вероятность каждого из событий «после этапа разбиения элемент, вы­ступавший в качестве разбивающего, занимает в массиве i-е место»,

i = 1, 2,..., п, равна -. п

Это обстоятельство позволяет переформулировать задачу анализа сложности рандомизированной быстрой сортировки, например, сле­дующим образом. Имеется полоска бумаги шириной в одну клетку и длиной в п клеток, n ^ 0, которую надо разрезать на отдельные клетки. Разрезы имеет право производить некий разрезальщик, ко­торому надо платить за работу. При п = 0 или п = 1 разрезальщик ничего не делает и ничего не получает. В случае п > 1 он выбирает случайным образом (тянет из шапки билет с номером) значение i из множества {1, 2, ...,п} и затем вырезает из полоски i-ю клетку (рис. 8), получая за этот этап работы вознаграждение вп-1 рубль. Кроме вырезанной клетки возникают две полоски, длина каждой из

		m

Рис. 8. Этап разрезания полоски.