С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 11
Текст из файла (страница 11)
Поэтому сложность в среднем по числу перемещений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 → ∞ сложность в среднемможет расти существенно медленнее, чем сложность в худшем случае.Пример .. Рассмотрим сложность в среднем ¯T¯QS (n) быстрой сортировки по числу сравнений. Будем считать, что в качестве разбивающего элемента всегда выбирается первый элемент сортируемой частимассива. Введем случайную величину ξn на Πn , равную числу сравTнений быстрой сортировки для a ∈ Πn (в этом смысле ξn (a) = CQS(a)).ИмеемX¯T¯QS (n) = Eξn = 1ξn (a).n!a∈ΠnВведем разложениеΠn = Kn1 + Kn2 + ...
+ Knn ,где событию Kni принадлежат все те перестановки длины n, для которых разбивающий элемент занимает i-ю позицию после завершенияразбиения. В силу предложения .(i) (видно, что Kni = Fni,1 — событиесостоит в том, что -й элемент перестановки равен i), получаем1nPn (Kni ) = ,i = 1, 2, ..., n.Разбиение перестановки a (первый этап быстрой сортировки) порождает две перестановки a′ ∈ Πi−1 и a′′ ∈ Πn−i . В соответствии с этимопределим еще две случайные величиныξ′n (a) = ξi−1(a′ ),ξ′′n (a) = ξn−i (a′′ ),где i — номер позиции, которую занимает разбивающий элемент после разбиения.
По формуле полного математического ожиданияEξ n =nXi =1E(ξn | Kni )Pn (Kni ) =nX1(n − 1 + E(ξ′n | Kni ) + E(ξ′′n | Kni )) ;i =1nГлава . Сложность в среднемпосле очевидного упрощения имеемEξ n = n − 1 +1nnXi =1(E(ξ′n | Kni ) + E(ξ′′n | Kni )).Займемся вычислением E(ξ′n | Kni ) и E(ξ′′n | Kni ), 1 ¶ i ¶ n.Мы имеем разложениеXKni =Gni,p ,p ∈Πi−1i,pгде событие Gn определено так же, как в предложении .(ii), — этособытие состоит в том, что относительный порядок элементов перестановки, имеющих значения, меньшие i, совпадает с порядком элементов перестановки p длины i − 1; имеемXE(ξ′n | Kni ) =E(ξ′n |Gni,p )Pn (Gni,p ).p ∈Πi−1i,pКогда выполняется Gn , значение ξ′n (a) равно ξi−1 (p).
Принимая дополнительно во внимание предложение .(ii), имеемX1= E ξ i −1 .E(ξ′n | Kni ) =ξi−1 (p)(i − 1)!p ∈Πi−1Аналогично можно показать, чтоXξn−i (p)E(ξ′′n | Kni ) =p ∈Πn−i1= Eξ n − i ;(n − i)!здесь надо рассмотреть событие, которое состоит в том, что относительный порядок элементов перестановки, имеющих значения, большие i, совпадает с порядком элементов перестановки p длины n − i.В итоге получаемEξ n = n − 1 +Так какnPi =1E ξ i −1 =nPi =1Eξ n − i =1nnP−1nXi =1(Eξi−1 + Eξn−i ).Eξk , тоk =0Eξ n = n − 1 +2nn −1Xk =0Eξ k .(.)§ . Пример медленного роста сложности в среднемТаким образом, для ¯T¯QS (n) = Eξn мы имеем соотношениеn −1X¯T¯QS (k),¯T¯QS (n) = n − 1 + 2n(.)k =0¯T¯QS (0) = 0. Домножение обеих частей равенства (.) на n даетn¯T¯QS (n) = n(n − 1) + 2n −1X¯T¯QS (k).k =0При n > 0 имеем для n − 1:(n − 1)¯T¯QS (n − 1) = (n − 1)(n − 2) + 2n −2X¯T¯QS (k).k =0Вычитая почленно последнее равенство из предпоследнего, получаемn¯T¯QS (n) − (n − 1)¯T̄QS (n − 1) = 2(n − 1) + 2¯T¯QS (n − 1),т.
е.n¯T¯QS (n) − (n + 1)¯T¯QS (n − 1) = 2(n − 1).Делим последнее равенство на n(n + 1) и переходим к новой неизвестной функции t(n) =¯T¯QS (n):n+1t(n) − t(n − 1) = 2n−1,n(n + 1)t(0) = 0.Решением любого уравнения вида t(n) − t(n − 1) = ϕ (n) при функцииnPϕ , определенной для всех n ¾ n0 , является t(n) = ϕ (n0 ) +ϕ (k),k = n 0 +1n ¾ n0 (легко доказывается индукцией по n в предположении, что если нижний предел суммирования больше верхнего, то сумма равнанулю). В нашем случаеt(n) = 2nXk =1Мы имеемnPk =1поскольку рядотсюдаk−1=2k(k + 1)nXk =11−2k+1nXk =11.k(k + 1)(.)nP11= ln n + O(1); с другой стороны,= O(1),k+1k(k+ 1)k =1∞Pk =11сходится. Таким образом, t(n) = 2 ln n + O(1);k(k + 1)¯T¯QS (n) = (n + 1)t(n) = 2n ln n + O(n).(.)Глава .
Сложность в среднемВ то же время, сложность в худшем случае TQS (n) есть величина порядка n2 (см. задачу ).Число перемещений, требуемое быстрой сортировкой для конкретного массива, не превосходит числа сравнений, домноженногона некоторую небольшую константу, откуда сложность в среднем¯T¯′ (n) по числу перемещений элементов допускает оценку ¯T¯′ (n) =QSQS= O(n log n).Сложность в среднем быстрой сортировки как по числу сравнений,так и по числу перемещений элементов допускает оценку O(n log n).Быстрая сортировка не использует дополнительных массивов, поэтому пространственная сложность по числу одновременно хранимыхдополнительных величин, равных каким-то элементам исходного массива, ограничена (небольшой) константой и, как следствие, допускает оценку O(1).Нелишне заметить, что если быстрая сортировка реализована какрекурсивная процедура, то при ее выполнении будет использованстек отложенных заданий.
Рекурсию в данном случае можно организовать так, что в стек будут попадать лишь значения индексов некоторых элементов, но не сами элементы массива. В соответствии с определением алгебраической сложности объем такого стека не влияет напространственную сложность.Если выйти за рамки алгебраической сложности, то размер стекаотложенных заданий становится важной характеристикой алгоритма. Мы рассмотрим размер этого стека для некоторого типа рекурсивных сортировок, к которому относится не только быстрая сортировка, но и, например, рекурсивный вариант сортировки слияниями.Пусть сортировка организована так, что на первом ее этапе мы, следуя некоторому принципу, выделяем из массива x длины n > 1 двекакие-то его непересекающиеся части x ′ , x ′′ , длина каждой из которых меньше n. На втором этапе эти части сортируются рекурсивнос помощью той же сортировки, и на третьем, заключительном, этапе,исходя из результатов сортировки x ′ и x ′′ , массив x представляется,уже без рекурсий, в упорядоченном виде.
Если n = 0 или n = 1, тоникаких действий над элементами массива не производится.Будем использовать для такого рода сортировок рабочее название«бинарные рекурсивные сортировки». Возникающие при выполнениитаких сортировок рекурсии реализуются с помощью стека отложенных заданий.Теорема .. Если некоторая бинарная рекурсивная сортировкатакова, что первым из x ′ , x ′′ сортируется массив, имеющий не пре-§ . Пример медленного роста сложности в среднемnдлину, то в ходе применения сортировки к массиву xвосходящую2длины n > 1 число отложенных заданий, хранящихся в стеке, никогдане превосходит log2 n.Доказательство.
Проведем индукцию по n. При n = 2 утверждение, очевидно, справедливо. Пусть утверждение доказано для2, 3, ..., n − 1, и пусть массив x, содержащий n элементов, на первомэтапе сортировки порождает два массива x ′ , x ′′ , причем длина n′nпервого массива x ′ не превосходит , длина n′′ второго массива x ′′2не превосходит n − 1. Пусть n′′ ¾ n′ ¾ 1. На протяжении сортировкимассива x ′ , помимо отложенных заданий, связанных с сортировкойx ′ , в стеке будет храниться еще одно задание — сортировать x ′′ .Но в момент, когда сортировка массива x ′ завершена, в стеке неостанется никаких ее следов; таким образом, по предположениюиндукции, число отложенных заданий в стеке никогда не превзойnдет max{log2 n′ + 1, log2 n′′ }.
В силу того, что n′ ¶ и n′′ ¶ n − 1, мы2имеемmax{log2 n′ + 1, log2 n′′ } ¶ log2 n,что и требовалось.Полученная оценка числа отложенных заданий, хранящихся в стеке, является оценкой для сложности в худшем случае и, тем самым,для сложности в среднем тоже.Принимая во внимание теорему ., мы приходим к варианту быстрой сортировки, представляемому рекурсивной процедурой qsort(k, l),обращение к которой обеспечивает сортировку части xk , xk+1 , ..., xl исходного массива x1 , x2 , ..., xn ; при k ¾ l никаких действий не производится. Сам массив x1 , x2 , ..., xn является глобальным по отношениюк процедуре:if k < l thenxk выбирается в качестве разбивающего элемента и выполняется разбиение xk , xk+1 , ..., xl ; пусть i — индекс, получаемый разбивающим элементом после разбиения;if i − k < l − i then qsort(k, i − 1); qsort(i + 1, l) elseqsort(i + 1, l); qsort(k, i − 1)fifi.Быстрая сортировка всего массива является результатом выполненияqsort(1, n).Глава .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
