Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

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

Вновь обратимся к быстрой сортировке. В §  нами установлено, что быстрая сортировка имеет сравнительно низкуюсложность в среднем в предположении, что для каждого 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, представленного на рис. , мы назовем s′ и s′′ левым и правым подсценариями. При n > 1 определимна Sn дополнительно к χn еще две случайные величины χn′ и χn′′ , положив χn′ (s) = χi−1 (s′ ) и χn′′ (s) = χn−i (s′′ ), где s′ и s′′ суть левый и правыйподсценарии сценария s. Имеем при n > 1χn (s) = n − 1 + χn′ (s) + χn′′ (s).Пусть n > 1. Введем разложениеSn = S1n + S2n + ... + Snn ,(.)где Sin — это событие «левый подсценарий данного n-сценария является (i − 1)-сценарием (и соответственно правый подсценарий является(n − i)-сценарием)», i = 1, 2, ..., n. Очевидно,1nPn (S1n ) = Pn (S2n ) = ...

= Pn (Snn ) = ,поэтому по формуле полного математического ожидания получаемEχ n =nXi =11nE(χn |Sin ) =1=n−1+n=n−1+1n=n−1+2nnXi =1nXi =1nXi =1(E(χn′ |Sin ) + E(χn′′ |Sin )) =( E χ i −1 + E χ n − i ) =E χ i −1 = n − 1 +2nn −1Xk =0Eχ k .§ . Функция затрат рандомизированного алгоритмаИтак,Eχ n = n − 1 +2nn −1XEχ k ,Eχ0 = 0.k =0Такого вида соотношения уже встречались в предыдущем параграфе,и по аналогии с (.) мы находимEχn = 2n ln n + O(n).(.)Возвратимся к рандомизированной быстрой сортировке. Для данного массива длины n математическое ожидание затрат, измеряемыхчислом сравнений, полностью определяется значением n.

Поэтому,например, сложность в худшем случае, т. е. максимум математических ожиданий рассматриваемого вида для массивов длины n, естьпросто математическое ожидание, найденное при рассмотрении этого n. Мы можем переписать (.) как соотношение для сложностиTeQS (n) по числу сравнений рандомизированной быстрой сортировки:TeQS (n) = 2n ln n + O(n).Вновь можно заметить, что число перемещений, требуемое рандомизированной быстрой сортировкой для конкретного массива, непревосходит числа сравнений, домноженного на некоторую констан′ту, откуда сложность в среднем TeQS(n) по числу перемещений эле′eментов допускает оценку TQS (n) = O(n log n). Как и обычная быстраясортировка, рандомизированная быстрая сортировка не используетдополнительных массивов, поэтому S̃QS (n) = O(1).Сложность рандомизированной быстрой сортировки как по числусравнений, так и по числу перемещений элементов допускает оценку O(n log n).

Пространственная сложность по числу одновременнохранимых дополнительных величин, равных каким-то элементам исходного массива, допускает оценку O(1).При использовании принципа «из двух заданий первым выполняется более простое», мы получаем, согласно теореме ., для сложности по объему стековой памяти оценку log2 n.Совпадению сложностей ¯T¯QS (n) и TeQS (n) можно дать объяснение: случайный выбор разбивающего элемента, предпринимаемыйна каждом этапе сортировки, эквивалентен тому, что мы меняемпорядок исходного массива случайным образом и затем применяем«обычную» быструю сортировку; но равенство сложностей такого рода не обязано иметь место для других алгоритмов, — все-таки речьидет о математических ожиданиях случайных величин, определенныхГлава .

Сложность в среднемна разных вероятностных пространствах. Например, можно несколько ускорить рандомизированную быструю сортировку, если разбивающий элемент определять путем случайного выбора без возвращениятрех элементов массива и последующего определения второго по величине из этих трех; можно показать, что тогда вместо 2n ln n + O(n)12n ln n + O(n)  , и совпадения сложностей обычной и ранвозникнет7домизированной быстрой сортировки уже не будет.Возвращаясь к примеру ., мы видим, что, основываясь на рандомизированной быстрой сортировке, можно получить алгоритм построения выпуклой оболочки данных n точек координатной плоскости,имеющий сложность в среднем O(n log n) по общему числу операций.При нахождении или оценивании сложности какого-либо рандомизированного алгоритма часто не возникает необходимости детальногорассмотрения всевозможных сценариев. Бывает достаточно рассмотреть сходное с (.) разложение пространства сценариев и применитьформулу полного математического ожидания.

Даже если множествовсех сценариев бесконечно, разложение вида (.) можно выбрать конечным.Пример .. Массив x1 , x2 , ..., xn назовем массивом, содержащимбольшинство, если больше половины его элементов имеют равныезначения. Пусть над элементами массивов разрешена операция проверки равенства двух элементов, будем называть эту операцию сравнением. Пусть для данного массива, содержащего большинство, требуется найти i, 1 ¶ i ¶ n, такое, что значение xi принадлежит большинству значений элементов x1 , x2 , ..., xn . Один из возможных рандомизированных алгоритмов решения этой задачи состоит в том,что i выбирается случайно (распределение вероятностей равномерно), а затем проверяется, удовлетворяет ли xi поставленному условию, — сравнений на эту проверку уйдет не более n − 1.

Если xi неподходит, то все повторяется. Сложность в среднем по числу сравнений этого алгоритма не превосходит 2(n − 1). В самом деле, пространство всех сценариев разлагается на два события: первая попытка найти нужное i оказывается удачной и, соответственно, эта попытка оказывается неудачной. По формуле полного математическогоожидания имеем для искомого среднего a:1pa ¶ p(n − 1) + (1 − p)(a + n − 1).Отсюда a ¶ (n − 1) < 2(n − 1).Доказательство имеется, например, в [, разд.

Характеристики

Список файлов лекций