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

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

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

, мы назовем 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).Доказательство имеется, например, в [, разд. .].ЗадачиЕще один путь получения этого же результата. Так как вероятность p удачного выбора индекса i больше половины, то математическое ожидание количества попыток, которые потребуются для получения удачного значения i, меньше двух.

Отсюда среднее число сравнений a меньше, чем 2(n − 1).Теоретически нет никакого препятствия к тому, чтобы при определении функции затрат рандомизированного алгоритма взять вместо математического ожидания максимум затрат по соответствующим сценариям (при таком подходе рандомизированная быстрая сортировка имеет квадратичную сложность). Но обычно длярандомизированных алгоритмов рассматриваются усредненные затраты.Добавим в заключение, что правомерен взгляд на рандомизированные алгоритмы, при котором каждому возможному входу сопоставляется вероятностное пространство обычных детерминированных алгоритмов  . Если в этой связи вернуться к примеру ., томожно заметить, что для разрезания полоски бумаги каждый из рассматриваемых сценариев задает конкретный детерминированный алгоритм разрезания.Мы вернемся к этому в § .Задачи.

Верно ли, что для рассмотрения сложности в среднем некоторого алгоритма требуется задание распределения вероятностейа) на множестве всех допустимых входов?б) на каждом из множеств всех входов фиксированного размера?. Как говорилось при обсуждении асимптотического закона распределения простых чисел, в [] приводится элементарное доказательство неравенств Чебышева с C = 6, c = 1/3. Добавим, что наиболее легко доказывается нижняя оценкаπ(n) >1 n,3 ln nсправедливая для всех n > 1.

Доказать, что сложность в среднем алгоритма пробных делений не является полиномиально ограниченной,используя для этого только последнее неравенство и не прибегаяк полному варианту асимптотического закона распределения простыхчисел.См., например, [].Глава . Сложность в среднемУказание. Предположение о том, что V (m) < 23m/4 для всех m > m0 , позволило бы, исходя из равенстваπ(2m ) = π(2m0 ) + V (m0 + 1) + V (m0 + 2) + ... + V (m),вывести верхнюю оценку π(2m ) = O(23m/4 ), что вступило бы в противоре2mчие с неравенством π(2m ) ¾ cс положительной константой c.

Поэтомуmсуществует последовательность m1 < m2 < ... натуральных чисел таких, чтоV (mi ) ¾ 23mi /4 , i = 1, 2, ... Можно рассмотреть (.) для m = m1 , m2 , .... Сложность по числу перемещений (обменов) в среднем длясортировки выбором при условии, что мы исключаем обмены вида1xk ↔ xk , не превосходит n − 2 + , где n — длина массива.nУказание. В перестановках из Πn среднее число элементов ai , 1 ¶ i ¶ n − 1,таких, что ai = i, естьn−1(см. пример .).n. Найти среднее число присваиваний m := ...

при выполненииалгоритма поиска наименьшего элемента массива:m := x 1 ;for i = 2 to n doif xi < m then m := xi fiodПредполагается, что все возможные взаимные порядки элементовв исходном массиве длины n являются равновероятными; в качестверазмера входа берется n.Указание. Рассмотреть разложение всего вероятностного пространства всумму двух событий: последний элемент исходного массива является его наи1меньшим элементом (вероятность равна ) и соответственно последний элеnмент исходного массива не является его наименьшим элементом (вероятn−1ность равна). Пусть s(n) обозначает искомое математическое ожидание.nПоказать, что условное математическое ожидание исследуемого числа присваиваний, соответствующее первому событию, есть s(n − 1) + 1, а условноематематическое ожидание, соответствующее второму событию, есть s(n − 1).Пользуясь формулой полного математического ожидания, вывести отсюда рекуррентное соотношение для s(n) и найти его решение, удовлетворяющееусловию s(1) = 1..

Пользуясь дискретным аналогом формулы Ньютона—ЛейбниnPца, согласно которому( f (k + 1) − f (k)) = f (n + 1) − f (1), вычислить суммуnPk =1k =11, входящую в (.).k(k + 1)Задачи. Исходя из (.), пользуясь приемом оценки сумм из приложения B и результатом из предыдущей задачи, доказать неравенство ¯T¯QS (n) ¶ 2n ln n, из которого будет следовать, что величина O(n)в правой части (.) отрицательна.. Вернемся к задаче .

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

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