С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 10
Текст из файла (страница 10)
Вещественная неотрицательная функция f (m),определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином P(m)с вещественными коэффициентами такой, что f (m) ¶ P(m) для всехm ∈ N+ . (Очевидно, что мы получим эквивалентное определение, еслидополнительно потребуем, чтобы все коэффициенты полинома P(m)были неотрицательными; другие эквивалентные варианты определения: f (m) = O(md ) для некоторого d ∈ N и f (m) = mO(1) .)Доказанное нами можно сформулировать так:Пусть в качестве размера входа алгоритма пробных делений, предназначенного для распознавания простоты натурального числа n,привлекается m = λ(n). Тогда временные сложности этого алгоритмакак в худшем случае, так и в среднем по числу делений не являютсяполиномиально ограниченными функциями от m.Краткое обсуждение идеи такого алгоритма распознавания простоты числа, который имеет полиномиально ограниченную сложность в худшем случае (тем самым, разумеется, и в среднем), будет проведено в примере ..
При этом речь пойдет не об алгебраической сложности по числу делений, мультипликативной сложности и т. д., а о битовой сложности, что приводит к существенно болеесильным утверждениям. До этого в гл. будет детально рассмотреносамо понятие битовой сложности.§ . Сортировка и конечные вероятностные пространства.Применение формулы полного математического ожиданияПри рассмотрении сложности в среднем мы, прежде всего, должныпревратить каждое из множеств входов, обладающих фиксированнымразмером, в вероятностное пространство. Проще работать с конечными вероятностными пространствами, но как обходиться такимипространствами, имея дело, например, с алгоритмами сортировки,входом каждого из которых, при фиксированном размере n, можетбыть любой массив x1 , x2 , ..., xn с попарно различными элементами?Общий принцип заключается в том, что мы разбиваем все имеющиефиксированный размер n входы на некоторые классы, включая в один§ . Сортировка и конечные вероятностные пространствакласс входы, неразличимые для данного алгоритма в том смысле, чтоалгоритм проделывает одну и ту же последовательность операций длялюбого входа, принадлежащего классу (этот принцип может применяться не только при рассмотрении той или иной сортировки).
Числотаких классов может оказаться конечным, даже если само множествовходов размера n бесконечно. Если это не противоречит другим предположениям, то такие классы можно рассматривать как элементарные события, приписывая каждому из них некоторую вероятность.На выполнение любой сортировки с помощью сравнений самизначения элементов x1 , x2 , ..., xn не оказывают никакого влияния, важен лишь их относительный порядок.
Поэтому в один класс естественно объединять все массивы x1 , x2 , ..., xn , имеющие один и тотже порядок элементов по отношению друг к другу. Такой класс может быть представлен перестановкой чисел 1, 2, ..., n с соответствующим порядком элементов (перестановкой длины n). В дальнейшемдля любого n ∈ N∗ мы будем рассматривать функцию ψn , аргументами которой являются любые попарно различные числа x1 , x2 , ..., xn ,а значением — перестановка a = (a1 , a2 , ..., an ) чисел 1, 2, ..., n, отражающая относительный порядок чисел x1 , x2 , ..., xn . Например,3(.)ψ3 − , −10, 17 = (2, 1, 3).4Множество всех перестановок чисел 1, 2, ..., n будет обозначаться через Πn , так же будет обозначаться и вероятностное пространство,1получаемое приписыванием вероятностикаждой из этих перестаn!новок.Рассмотрим некоторые события в вероятностном пространстве Πn ;Mвероятность каждого из них, очевидно, будет равна , где M — чисn!ло перестановок, составляющих событие.
Эту вероятность мы будемобозначать через Pn (·).Пример .. Начнем с события Bvn , 1 ¶ v ¶ n, состоящего в том,что v-й элемент av перестановки (a1 , a2 , ..., an ) равен v. Перестановку (a1 , a2 , ..., an ) ∈ Πn можно рассматривать как отображение множества {1, 2, ..., n} на себя, при котором 1 переходит в a1 , переходитв a2 и т.
д., и событие Bvn состоит тогда в том, что v является неподвижной точкой перестановки. Множество, состоящее из перестановок (a1 , a2 , ..., an ) таких, что av = v, содержит (n − 1)! элементов, от(n − 1)!1= при всех рассматриваемых v.сюда Pn (Bvn ) =n!nВ зависимости от выбранной перестановки число неподвижныхточек может быть любым целым из диапазона от 0 до n. РассмотримГлава . Сложность в среднемвопрос о среднем числе неподвижных точек перестановок длины n:найдем математическое ожидание определенной на Πn случайной величины ξn , равной числу неподвижных точек перестановки a.
Дополнительно определим случайные величины¨1, если av = v,vζn =0, если av 6= v,1nv = 1, 2, ..., n. Мы видим, что Pn (ζvn = 1) = Pn (Bvn ) = , откуда Eζvn =Eξn = E(ζ1n + ζ2n + ... + ζnn ) = Eζ1n + Eζ2n + ... + Eζnn = n ·1иn1= 1.nИтак, среднее число неподвижных точек равно 1. Неподвижные точки перестановки соответствуют элементам массива, которые при сортировке не нуждаются в перемещениях на другие места, они и так находятся именно там, где должны находиться,и это может использоваться в некоторых видах сортировки (см. задачу ).Найдем теперь вероятности еще трех событий — эти вероятностипотребуются нам при исследовании сложностей в среднем некоторыхсортировок.Предложение ..
Пусть n ∈ N+ . Тогда(i) при 1 ¶ u ¶ n, 1 ¶ v ¶ n имеемPn (Fnu,v ) =1nдля события Fnu,v , состоящего в том, что v-й элемент перестановки(a1 , a2 , ..., an ) равен u;(ii) при 1 < u ¶ n и любой перестановке p чисел 1, 2, ..., u − 1 имеемPn (Gnu,p ) =u,p1(u − 1)!для события Gn , состоящего в том, что относительный порядокэлементов ai1 , ai2 , ..., aiu−1 перестановки (a1 , a2 , ..., an ), меньших u, совпадает с относительным порядком элементов заданной перестановки p (аналогичное утверждение имеет место для элементов, больших u);(iii) при 0 ¶ u < v ¶ n имеемPn (Hnu,v ) =1vСерия вероятностных «задач о совпадении» с решениями приведена в [].§ . Сортировка и конечные вероятностные пространствадля события Hnu,v, состоящего в том, что в перестановке (a1, a2 , ..., an )содержится u элементов ai , 1 ¶ i < v, для которых ai < av .Доказательство.
(i) Множество перестановок (a1 , a2 , ..., an ) таких,что av = u, содержит (n − 1)! элементов, независимо от значенийu и v.nu,p(ii) Событие Gn включает(n − u + 1)! перестановок, т. е.u−1n!перестановок, независимо от вида p.(u − 1)!(iii) Очевидно, что если p — любая перестановка чисел 1, 2, ..., v,то множество перестановок(a1 , a2 ..., an ) таких, что ψv (a1 , a2 , ..., av ) = nn!элементов (мы используем функ= p, содержит(n − v)! =v!vцию ψv , определенную перед формулой (.)). Заметим, что количество тех перестановок p чисел 1, 2, ..., v, в которых последний элемент равен u + 1, есть (v − 1)!.
Поэтому количество перестановок,n!n!образующих событие Hnu,v , равно(v − 1)!, т. е., откуда следуетv!vтребуемое.Напомним полезную формулу из курса теории вероятностей. Каки прежде, мы ограничимся рассмотрением конечных вероятностных пространств элементарных событий. Пусть W — такое пространство, P — соответствующее распределение вероятностей, ξ — некоторая случайная величина (функция) на W .
Пусть события W1 , W2 , ..., Wlзадают полную группу событий, т. е. эти события попарно несовместны иW = W1 + W2 + ... + Wl .(.)Представление W в виде (.) с помощью некоторой полной группысобытий мыP будем называть разложением W . Как обычно, Eξ — этозначениеξ(w)P(w), т. е. математическое ожидание (или среднее)w ∈Wслучайной величины ξ, а E(ξ|Wk ), k = 1, 2, ..., l, суть соответствующиеусловные математические ожидания этой случайной величины (приусловии осуществления события Wk ).
Тогда, как известно, имеет место формула полного математического ожидания:Eξ =lXE(ξ|Wk )P(Wk ).(.)k =1Оценивание математических ожиданий является оцениванием числовых сумм. В этом иногда помогает простой прием, описанный в приложении B.Глава . Сложность в среднемПример .. Исследуем сложности в среднем по числу сравнений и перемещений сортировки простыми вставками, которую, каки прежде, мы будем рассматривать в двух вариантах I1 и I2 (см. пример .). Вначале займемся первым вариантом I1 этой сортировки,полагая затраты равными числу сравнений.
Входные массивы считаем перестановками чисел 1, 2, ..., n. Для исследования сложности почислу сравнений введем случайные величины ξ1n , ξ2n , ..., ξnn−1 , определенные так, что значение ξin дляa = (a1 , a2 , ..., an ) ∈ Πnравно затратам на i-м шаге нашей сортировки, применяемойк a. Ясно, что интересующее нас математическое ожидание естьE(ξ1n + ξ2n + ... + ξnn−1 ), и¯T¯I (n) = Eξ1 + Eξ2 + ... + Eξn−1 .nnn1(.)Найдем ξin , 1 ¶ i < n.
Рассматривая события Hnk,i+1, k = 0, 1, ..., i, образующие разложение пространства Πn , и применяя формулу (.)полного математического ожидания, мы имеем согласно предложению .(iii)iX1E(ξin | Hnk,i+1 ).(.)Eξin =i+1k =0Если перестановка a = (a1 , a2 , ..., an ) принадлежит событию Hnk,i+1 , тов этой перестановке перед элементом ai+1 имеется ровно k элементов,меньших его, и, очевидно,¨i − k + 1, если k > 0,iξn =i,если k = 0.Мы видим, что при выполнении события Hnk,i+1 значение ξin определено однозначно (напомним, что значение ξin , i = 1, 2, ..., n − 1, равночислу сравнений на i-м шаге, а перед выполнением i-го шага элементы a1 , a2 , ..., ai уже упорядочены по возрастанию). Поэтому¨i − k + 1, если k > 0,k,i +1iE(ξ n | H n ) =i,если k = 0.В соответствии с (.)Eξin =1i+i+1iXk =11i.(i − k + 1) = + 1 −2i+1§ .
Сортировка и конечные вероятностные пространстваИспользуя (.), получаем выражениеn−1+n −1 Xi =11i−2i+1для искомой сложности в среднем. С помощью известной из математического анализа формулы (ее вывод имеется в приложении B)nX1= ln n + O(1)i =1iсложность ¯T¯I1 (n) можно записать в виде¯T¯I (n) = (n + 4)(n − 1) − ln n + O(1)1(.)2¯T¯I (n) = n + O(n).1(.)4и, проще, в виде4Таким образом, сложность в среднем по числу сравнений первого варианта сортировки простыми вставками, как и сложность в худшемслучае, есть величина порядка n2 , но при больших n первая сложность примерно вдвое меньше второй. Формула (.) показывает, что,вообще говоря, вопреки бытовым представлениям сложность в среднем не есть среднее арифметическое затрат в худшем и в лучшем случае: такое среднее арифметическое для рассматриваемой сортировкиявляется рациональной функцией от n и не может описываться этойформулой, содержащей логарифм.Если рассмотреть вместо случайных величин ξ1n , ξ2n , ..., ξnn−1 случайные величины η1n , η2n , ..., ηnn−1 , соответствующим образом отражающие затраты исследуемой сортировки по числу перемещений, то,очевидно, будем иметьξin ¶ ηin ¶ ξin + 1,i = 1, 2, ..., n − 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
