С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 12
Текст из файла (страница 12)
Сложность в среднем§ . Функция затрат рандомизированного алгоритмаОпределение .. Алгоритмы с элементами случайности, реализуемыми обращениями к генераторам случайных чисел, называютсярандомизированными.Рандомизированные алгоритмы можно разделить на вероятностные, или, что то же самое, алгоритмы типа Монте-Карло, и алгоритмытипа Лас-Вегас. Первый тип допускает, что ответ, который дает алгоритм для поставленной задачи с некоторым конкретным входом, можетбыть неправильным, хотя бы и с малой вероятностью; второй тип —Лас-Вегас — гарантирует правильный ответ, но (как и для алгоритмовтипа Монте-Карло) время получения ответа для конкретного входане определяется, вообще говоря, однозначно этим входом .
Исключаяспециально оговариваемые редкие случаи, мы будем рассматриватьтолько алгоритмы типа Лас-Вегас, не упоминая этого каждый раз.Анализ сложности рандомизированного алгоритма сводится к нахождению математических ожиданий некоторых случайных величин.Но ситуация здесь отличается от той, когда множество входов фиксированного размера рассматривается как вероятностное пространство и затраты алгоритма, однозначно определенные для каждогоконкретного входа, становятся случайными величинами на этом пространстве (мы шли этим путем в двух предыдущих параграфах). Приисследовании рандомизированных алгоритмов вероятностное пространство, на котором рассматриваются случайные величины, состоит из сценариев выполнения алгоритма для фиксированного входа,и каждый сценарий определяется тем, какие случайные числа будут сгенерированы в соответствующие моменты выполнения алгоритма; за каждым таким сценарием закрепляется некоторая вероятность. В нашем контексте генератор случайных чисел можно представлять себе как стандартную функцию random(N) целого положительного аргумента N, результатом выполнения которой является элемент множества {0, 1, ..., N − 1}, но невозможно предсказать точно,каким именно будет значение этой функции, — любой из элементовуказанного множества может появиться с вероятностью 1/ N.Таким образом, затраты рандомизированного алгоритма при фиксированном входе, вообще говоря, не определяются однозначно, ноЭта классификация является достаточно распространенной в специальной литературе по рандомизированным алгоритмам — см., например, книгу [], — но не единственной.
Например, в [, разд. .] рандомизированные алгоритмы подразделяютсяиначе, а именно — на алгоритмы типа Монте-Карло, типа Лас-Вегас и шервудские. Мыне будем останавливаться на этом.§ . Функция затрат рандомизированного алгоритмазависят от сценария вычисления. При фиксированном входе мы можем рассмотреть множество всех сценариев и, приписав адекватнымобразом каждому из сценариев некоторую вероятность, ввести на полученном вероятностном пространстве случайную величину, значение которой для данного сценария равно соответствующим вычислительным затратам. Значение функции затрат на данном входе можноположить равным математическому ожиданию этой случайной величины (усредненным затратам для данного входа).
А после того какопределена функция затрат и принято соглашение о том, что такоеразмер входа, мы можем, как обычно, рассматривать сложность алгоритма — в худшем случае или же в среднем (последнее возможно,если только множество входов каждого фиксированного размера является вероятностным пространством).Мы не будем здесь сколь-либо глубоко входить в общие проблемы теории сложности рандомизированных алгоритмов, а ограничимся рассмотрением примеров, в которых вероятностное пространствосценариев является одним и тем же для каждого из входов данногоразмера (в общем случае это не так).Пример .. Вновь обратимся к быстрой сортировке.
В § нами установлено, что быстрая сортировка имеет сравнительно низкуюсложность в среднем в предположении, что для каждого n > 0 все относительные порядки элементов входных массивов длины n имеют1. Но в некоторых практических задачаходинаковую вероятностьn!это предположение может оказаться безосновательным в силу того,что все входные массивы изначально оказываются, например, «почтиупорядоченными».
Число сравнений, затрачиваемых быстрой сортировкой на каждом таком «почти упорядоченном» массиве, будет близко к n2 , что сведет на нет достоинства быстрой сортировки.Однако если разбивающий элемент выбирать случайно, то прикаждом фиксированном входе размера n усредненные затраты будутиметь порядок n log n, что и будет показано ниже. Итак, под рандомизированной быстрой сортировкой мы будем понимать быструюсортировку со случайным выбором индекса разбивающего элемента;если надо выбрать случайное значение m из k, k + 1, ..., l, то мы полагаем m := k + random(l − k + 1).
В том алгоритме, который записанв виде процедуры в конце § , вместоxk выбирается в качестве разбивающего элемента и выполняется разбиение xk , xk+1 , ..., xl ; пусть i — индекс, получаемый разбивающим элементом после разбиения;Глава . Сложность в среднемможно написатьm := k + random(l − k + 1);xm выбирается в качестве разбивающего элемента и выполняется разбиение xk , xk+1 , ..., xl ; пусть i — индекс, получаемыйразбивающим элементом после разбиения;это даст рандомизированный вариант быстрой сортировки.Пусть дан массив x1 , x2 , ..., xn попарно различных чисел.
Пусть мывыбираем элемент m из множества {1, 2, ..., n} и вероятность выбора1каждого из элементов есть . Тогда место xm в массиве x1 , x2 , ..., xnnпосле сортировки этого массива может оказаться любым с одной1и той же вероятностью . В самом деле, пусть 1 ¶ i ¶ n и пусть l(i) таnково, что xl(i) занимает после сортировки массива место с номером i.Это l(i) определяется единственным образом. Поэтому вероятностьпопадания xm после сортировки массива на i-е место равна вероят1ности того, что m = l(i).
Последняя вероятность, очевидно, равна .nСледовательно, приписывание одинаковой вероятности каждому возможному выбору индекса разбивающего элемента ведет к тому, чтовероятность каждого из событий «после этапа разбиения элемент, выступавший в качестве разбивающего, занимает в массиве i-е место»,1i = 1, 2, ..., n, равна .nЭто обстоятельство позволяет переформулировать задачу анализасложности рандомизированной быстрой сортировки, например, следующим образом. Имеется полоска бумаги шириной в одну клеткуи длиной в n клеток, n ¾ 0, которую надо разрезать на отдельныеклетки. Разрезы имеет право производить некий разрезальщик, которому надо платить за работу. При n = 0 или n = 1 разрезальщикничего не делает и ничего не получает.
В случае n > 1 он выбираетслучайным образом (тянет из шапки билет с номером) значение iиз множества {1, 2, ..., n} и затем вырезает из полоски i-ю клетку(рис. ), получая за этот этап работы вознаграждение в n − 1 рубль.Кроме вырезанной клетки возникают две полоски, длина каждой изiРис. . Этап разрезания полоски.§ . Функция затрат рандомизированного алгоритмакоторых не превышает n − 1, при этом не исключается равенствонулю одной из длин. С каждой из двух полосок разрезальщик проделывает ту же операцию, получая вознаграждение в соответствиис тем же принципом оплаты.
Каково математическое ожидание размера вознаграждения, получаемого разрезальщиком за всю работу?Здесь при фиксированном n множество всех возможных сценариев (будем называть их n-сценариями) — это фактически множество30302013211031020310201Рис. . Сценарии разрезания полоски из трех клеток (-сценарии).некоторых двоичных деревьев; на рис. показано одно из возможных представлений множества всех -сценариев. В каждой вершинедерева записывается число клеток в полоске.nПри произвольном n ¾ 0 понятие n-сценарияопределяется рекурсивно: -сценарий и -сценарий — это одна вершина, которой приписано число 0 или соответственно 1; пусть n > 1,тогда любой n-сценарий s получается выбоi −1n−iром некоторого числа i, 1 ¶ i ¶ n, некоторого(i − 1)-сценария s′ и некоторого (n − i)-сценаs′s′′рия s′′ : из корня n исходят ребра к вершинамi − 1 и n − i, к которым подклеиваются корниРис.
. Структурасценариев s′ и s′′ (рис. ). Каждому n-сценаn-сценария.рию s естественным образом приписываетсявероятность Pn (s) (здесь индекс n указываетна то, что вероятность соотнесена с некоторым n-сценарием): еслиn = 0 или n = 1, то сценарии имеют вероятность 1, а при n > 11nPn (s) = Pi−1 (s′ )Pn−i (s′′ ).(.)Например, третий из -сценариев, изображенных на рис. , имеет11вероятность , каждый из остальных — вероятность .36Формула (.) отражает идею алгоритма, а именно что после определения i выбор (i − 1)-сценария s′ и выбор (n − i)-сценария s′′ независимы друг от друга.
Эта формула превращает множество всех n-сценариев при фиксированном n в вероятностное пространство Sn . Поль-Глава . Сложность в среднемPPn (s) = 1: призуясь индукцией по n, проверим, например, чтоs ∈ Snn = 0 и n = 1 это очевидно, при n > 1 имеемXs ∈ SnPn (s) =nXX1P (s′ )Pn−i (s′′) =n i −1′i =1 s ∈Si−1s′′ ∈Sn−i=1nn XXs′ ∈Si−1i =1Pi−1 (s′ ) Xs′′ ∈Sn−iPn−i (s′′ )=1nnXi =11 · 1 = 1.Плата за разрезание полоски длины n на отдельные клетки полностью определяется использованным n-сценарием, это задает случайную величину χn на Sn , и нас интересует математическое ожиданиеэтой величины. Для сценария s, представленного на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
