Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 11
Текст из файла (страница 11)
РассмотримГлава . Сложность в среднемвопрос о среднем числе неподвижных точек перестановок длины 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. Поэтому сложность в среднем по числу перемещенийn2+ O(n).
Нетрудно показать, что и сложности в среднемтоже есть4по числу сравнений и числу перемещений второго варианта сортиn2ровки простыми вставками равны+ O(n). Сложность в среднем по4суммарному числу сравнений и перемещений и для первого, и дляn2второго варианта есть+ O(n), поскольку для любых случайных2величин ξ, η, определенных на каком-либо вероятностном пространстве, выполняетсяE(ξ + η ) = Eξ + Eη .(.)Глава .
Сложность в среднемКаждая из сложностей в среднем как по числу сравнений, так и почислу перемещений для двух вариантов сортировки простыми вставn2ками (всего четыре сложности) есть+ O(n); каждая из сложно4стей в среднем по общему числу сравнений и перемещений для двухвариантов этой сортировки (всего две сложности) естьn2+ O(n).2Можно вспомнить, что в примере ., в котором мы рассматривали для двух вариантов сортировки простыми вставками их сложностив худшем случае по суммарному числу сравнений и перемещений, наблюдалась непохожая ситуация, чему имеется, повторимся, простоеобъяснение: в отличие от (.), равенство max(ξ + η) = max ξ + max η,вообще говоря, места не имеет.Общая формулировка установленного нами соотношения:Теорема .. Сложность в среднем некоторого алгоритма по суммарному числу операций нескольких различных типов равна суммесложностей в среднем этого алгоритма по числу операций каждоготипа в отдельности.Среди наиболее элементарных сортировок мы пока рассмотрелисложность в среднем только для сортировки простыми вставками.Сразу же можно добавить, что для сортировки выбором ее сложностипо числу сравнений в среднем и в худшем случае совпадают, так какчисло сравнений однозначно определяется длиной n массива.
Числосравнений на i-м этапе (i-м просмотре массива) пузырьковой сортировки равно n − i. Не сталкиваясь с большими трудностями, можнопоказать (см. задачу ), что математическое ожидание s(n) числапросмотров массива естьn−nXk =0k! kn−k.n!(.)Очевидно, что s(n) < n. С другой стороны,nXk =0k! kn−k¶n!Поэтому s(n) ¾ n −nX(n − 1)! kk =0n!=1nnXk =0k=n+1.2n+1n−1=.
Мы имеем22n−1¶ s(n) < n2и s(n) = Θ(n). Из этого следует, что сложность в среднем по числусравнений пузырьковой сортировки квадратична.§ . Пример медленного роста сложности в среднемСложности в среднем по числу сравнений пузырьковой сортировки, сортировок выбором и простыми вставками имеют одинаковыйпорядок со сложностями этих же сортировок в худшем случае (допускают оценку Θ(n2 )).§ . Пример медленного роста сложности в среднем в сравнениисо сложностью в худшем случаеСледующий пример показывает, что при n → ∞ сложность в среднемможет расти существенно медленнее, чем сложность в худшем случае.Пример ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
