С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 3
Текст из файла (страница 3)
Таккак в качестве разбивающего элемента всегда берём первый, то события K ni будут1совпадать с событиями Fni ,1 , откуда Pn K ni = Pn Fni ,1 = , i = 1,..., n . После разбиенияn′′′′исходная перестановка a разбивается на a и a , причём a ∈ Π i−1 , a′′ ∈ Π n−i .( )( )Введём случайные величины ξ n′ (a) = ξi−1 (a′) и ξ n′′(a) = ξ n−i (a′′) , тем самым мы останемся втом же вероятностном пространстве.}⎛ на разбиение⎜TQS (n) = Eξ n = ∑ E ξ n K Pn K = ∑ n − 1 + E ξ n′ K ni + E ξ n′′ K ni⎜i =1i =1⎝n1= n − 1 + ∑ E ξ n′ K ni + E ξ n′′ K nin i=1n(in) ( )[(Используя очевидный факт K ni =∑Gp∈Π i −1) ∑ξ() ∑ξE ξ n′′ K ni =получаемустанавливается, чтоEξ n = n − 1 +) ()]) (⎞)⎟⎟ ⋅ 1n =⎠, получаем:(E ξ n′ K ni =Откудаi, pn(ninp∈Π i −1p∈Π n −ii −1( p) ⋅1= Eξ i−1 ,(i − 1)!n −i( p) ⋅1= E ξ n −i .(n − i )!1 n∑ (Eξi−1 + Eξ n−i )n i=1nnn −1i =1i =1k =0∑ Eξi−1 = ∑ Eξ n−i = ∑ Eξ kможно переписать в следующем виде:13⇒.НепосредственнойTQS (n) = Eξ n = n − 1 +проверкой2 n −1∑ Eξk , чтоn k =0TQS (n) = n − 1 +2 n−1∑ TQS (k ) ,n k =0(*)причём, как не трудно видеть, TQS (0) = 0 (для упорядочения массива нулевой длины нетребуется ни одного сравнения).
Тогда, для n ≥ 1 , получаемTQS (n − 1) = n − 2 +2 n−2∑ TQS (k ) .n k =0(**)Домножим (*) на n и вычтем (**), умноженное на (n − 1) , тогда получим:nTQS (n) − (n − 1)TQS (n − 1) = n(n − 1) − (n − 1)(n − 2) + 2TQS (n − 1) ⇔144442444432 ( n −1)nTQS (n) − (n + 1)TQS (n − 1) = 2(n − 1)⇒Введём обозначение t (n) =t (n) − t (n − 1) =TQS (n)n +1TQS (n)n +1−TQS (n − 1)n=2(n − 1).n(n + 1), тогда предыдущее равенство перепишется в виде:2(n − 1), причём t (0) = 0 . Известно, что если t (n) − t (n − 1) = ϕ (n) для всехn(n + 1)n ≥ n0 , тогда t (n) = ϕ (n0 ) +n∑ϕ (k ) (доказывается по индукции) ⇒ для t (n) получаем:k =n0 +1nnk −111= 2∑− 2∑.k =1 k ( k + 1)k =1 k + 1k =1 k ( k + 1)nt ( n ) = 2∑nДля первого ряда из математического анализа известна оценка:1∑ i = ln n + O(1) , второй рядi =1сходится, а значит, может быть оценён через O(1) , в итоге получаем:t (n) = 2(ln n + O(1) ) − O(1) = 2 ln n + O (1) ⇒ TQS (n) = 2n ln n + O(n) .Получилась довольно приятная оценка, хоть и с участием логарифма.
Но, как говорилЛандау, «Курица не птица, логарифм не бесконечность».Для пространственной сложности верно SQS (n) = SQS (n) = O(1) .Рассмотрим пространственные затраты стека: т.к. алгоритм работает с отложеннымизадачами, то для его реализации потребуется стек, в который будут помещаться пары ( p, q)— сегменты массива, которые необходимо сортировать. Оказывается (что будет доказанониже), что если из двух получающихся после разбиения частей для обработки братьменьшую, откладывая бόльшую, то затраты не превзойдут log 2 n .Утверждение. Если бинарная рекурсивная сортировка такова, что после разбиения длясортировки выбирается меньшая часть, то количество отложенных в стеке задач непревзойдёт log 2 n .14n, при этом длинна длинного2n≤ n − 1 .
Пусть x′ — меньшая часть, длина которой равна n′ ≤ , x′′ — большая, длинной2n′′ ≤ n − 1 . Для сортировки выбираем x′ , x′′ откладывая в стек, тогда в стек попадётmax{log 2 n′ + 1, log 2 n′′} ≤ log 2 n , что и требовалось доказать.Доказательство: после разбиения длина короткого массива ≤Приведём алгоритм быстрой сортировки на псевдокоде:qsort(k,l):if k<l–1 thenxk выбирается в качестве разбивающего элемента,и выполняется разбиение xk,…,xl;пусть i — индекс, получаемый разбивающимэлементом после разбиения;if i–k–1<l–i then qsort(k,i-1); qsort(i+1,l)else qsort(i+1,l); qsort(k,i-1)fifiРандомизированные алгоритмы.Рассмотрим функцию random(N), возвращающую случайное число от 0 до N − 1 , с1вероятностью выпадения каждого.
Введём элемент рандомизации в алгоритм быстройNсортировки, тогда на псевдокоде он перепишется следующим образом:qsort(k,l):if k<l–1 thenm:=k+random(l-k+1);xm выбирается в качестве разбивающего элемента,и выполняется разбиение xk,…,xl;пусть i — индекс, получаемый разбивающимэлементом после разбиения;if i–k–1<l–i then qsort(k,i-1); qsort(i+1,l)else qsort(i+1,l); qsort(k,i-1)fifiДадим другую формулировку алгоритма быстрой сортировки:Пусть имеется полоска клетчатой бумаги размером 1× n клеток, которую требуетсяразрезать на отдельные клетки.
Разрезать может только специальный разрезальщик, причемза одну операцию он может вырезать одну любую клетку (с края или из середины). Привырезании клетки из середины полоска разбивается на две. За одно отрезание разрезальщикберёт (n − 1) рубль, где n — длинна полоски, из которой вырезается клетка. Цель —порезать всю полоску на клетки.В такой формулировке сложностью алгоритма является суммарное количество рублей,необходимых для работы разрезальщику.Сценарий для разрезаний удобно изобразить в виде двоичного дерева.
Для n = 3 (полоска из3-х клеток) получаем следующие варианты сценариев (3-сценарии):3333322220000111100110015Смежные вершины здесь обозначены числами, соответствующими количествам остающихсяклеток с одной и другой стороны, после того как одна из исходных будет вырезана.Любой n-сценарий получается из левого (i − 1) -сценария и правого (n − i ) -сценария:ni−1n−iОбозначим через S n множество всех n-сценариев.
При фиксированном n всем n-сценариямприписываются следующие вероятности:− если n = 0 или n = 1 , то Pn ( s ) = 1 ;− если n > 1 , то Pn ( s ) =Покажем,чтотак1Pi−1 ( s′) Pn−i ( s′′) .nвведённаявероятностьудовлетворяетусловию∑ P ( s) = 1s∈S nn.Доказательство проведём по индукции: для n = 0 и n = 1 утверждение верно поопределению; пусть для всех для k < n выполнено ∑ Pk ( s ) = 1 , покажем что для ns∈S kутверждение тоже верно:n∑ P (s) = {по определению} = ∑ ∑s∈S nni =1 s′∈Si −1s′′∈S n −i1Pi−1 ( s′) Pn−i ( s′′) =n⎛⎞⎜⎟n ⎜⎛⎞⎟ 1 n⎞ ⎛1= ∑ ⎜ ⎜⎜ ∑ Pi−1 ( s′) ⎟⎟ ⋅ ⎜⎜ ∑ Pn−i ( s′′) ⎟⎟ ⎟ = ∑1 ⋅1 = 1 .n i=1 ⎜ ⎝ s′∈Si −1⎟ n i=1s′′∈Sn −i424 434⎠ ⎝1442443⎠ ⎟⎜⎜ 1=1 по предполо=1 по предполо⎟⎝ жению индукции жению индукции ⎠Введём случайную величину χ n ( s ) — затраты алгоритма для сценария s.
Наряду с нейрассмотрим также случайные величины χ n′ ( s ) = χ i−1 ( s′) и χ n′′( s ) = χ n−i ( s′′) , определённые натом же вероятностном пространстве, что и χ n ( s ) .Изформулировкиалгоритмаследует,чтоχ n ( s) = n − 1 + χ n′ ( s ) + χ n′′( s) .Разложимвероятностное пространство S n следующим образом: S n = S n1 + ... + S nn , где S ni соответствуеттому, что левый сценарий является (i − 1) -сценарий, а правый — (n − i ) -сценарий.
Не трудно1проверить, что Pn ( S ni ) = , откуда получаем:nn() 1n = n − 1 + 1n ∑ [E(χ ′ S )+ E(χ ′′ S )] = n − 1 + 1n ∑ (EχnEχ n = ∑ E χ n S ni ⋅i =1i =1= n −1+т.е. получаем, что Eχ n = n − 1 +ninninni =1i −1+ E χ n −i ) =2 n2 n−11nEχ=−+∑ n −i∑ Eχ kn i=1n k =02 n−1∑ Eχ k , Eχ 0 = 0 . Откуда, аналогично предыдущему случаю,n k =0~получаем: TQS (n) = Eχ n = 2n ln n + O(n) .
В итоге получилось, что введение элементарандомизации никак не отразилось на сложности в среднем алгоритма быстрой сортировки.16Способы ускорения алгоритма быстрой сортировки.Если на каждой итерации выбирать 3 случайных элемента и брать серединный в качестверазбивающего, то в итоге сложность в среднем так модифицированного алгоритма составит12n ln n + O(n) .7Алгоритм Евклида (E).Рассмотрим алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух целыхположительных чисел a0 ≥ a1 , которые будут являться входом алгоритма. Алгоритмзаключается в последовательных делениях с остатком:a0 = q1a1 + a2a1 = q2 a2 + a3...an−3 = qn−2 an−2 + an−1an−2 = qn−1an−1 + anan−1 = qn anТогда an будет являться НОД, что легко показать по индукции:НОД(a0 , a1 ) = НОД(a1 , a2 ) = ... = НОД(an ,0) = an .Затраты алгоритма будем определять числом необходимых делений с остатком C E (a0 , a1 ) .Не трудно видеть, что C E (a0 , a1 ) ≤ a1 , т.к.
после первого деления остаток остаётся меньше a1 ,а при каждом следующем делении остаток будет меньше предыдущего как минимум на 1. Всвязи с этим в качестве входа можно взять только второе меньшее число a1 , тогда TE (a1 ) ≤ a1 .Один шаг алгоритма Евклида переводит пару ai−1 , ai в пару ai , ai+1 . Для оценки количествашагов алгоритма Евклида, которое совпадает с количеством необходимых делений состатком, хорошо было бы найти такую функцию λ (ai−1 , ai ) , для которой выполнялись быследующие условия:1. λ (ai −1 , ai ) ≥ 0 ;2. C E (ai−1 , ai ) ≤ λ (ai−1 , ai ) ;3. на каждом шаге алгоритма Евклида она уменьшается хотя бы на 1.Рассмотрим функцию λ (k , l ) = ν (k ) +ν (l ) − 2 , где ν (x) соответствует битовой длине x .Очевидно, что она удовлетворяет первым двум сформулированным условиям.
Убедимся всправедливости третьего. Справедливо следующееУтверждение. Пусть k, l ∈ N , k > l , r — остаток от деления1. ν (k ) > ν (r ) ;2. λ (k , l ) > λ (l , r ) .Доказательство:1. k = ql + r , q ≥ 1 ⇒ k ≥ l + r > 2r ⇒ ν (k ) > ν (l ) ;17k. Тогдаl2. ν (k ) > ν (r ) ⇒ ν (k ) + ν (l ) − 2 > ν (l ) + ν (r ) − 2 ⇔ λ (k , l ) > λ (l , r ) , что и требовалосьдоказать.C E (a0 , a1 ) ≤ λ (a0 , a1 ) = ν (a0 ) + ν (a1 ) − 2C E (a0 , a1 ) = CE (a1 , a2 ) + 1 ≤ ν (a1 ) + ν (a2 ) − 1 ≤ 2ν (a1 ) − 1123≤ν ( a1 )TE (a1 ) = max C E (a0 , a1 ) ≤ 2ν (a1 ) − 1 = 2 ⎣log 2 a1 ⎦ + 1a0 ≥a1Итак, для сложности алгоритма Евклида была получена оценка: TE (a1 ) = O (log a1 ) .
Возникаетвопрос: можем ли мы улучшить эту оценку? Ответ: нет, эта оценка точная. Длядоказательства точности оценки построим последовательность входов a0(1) , a1(1) , a0( 2) , a1( 2) ,(a)(()) (), a1( 3) , … такую, что для неё будет выполняться C E (a0( n ) , a1( n ) ) = Ω log a1( n ) при n → ∞ .
Длянаших целей хорошо подойдут числа Фибоначчи: F0 = 0 , F1 = 1 , Fn+2 = Fn+1 + Fn , т.е.последовательность 0, 1, 1, 2, 3, 5, 8, … Применяя алгоритм Евклида к паре (Fn+1 , Fn )получим ровно n делений: C E (Fn+1 , Fn ) = n . Используем формулу Бене:( 3)0Fn =()1 n1+ 5φ − (− φ )−n , где φ == 1,61803... («золотое сечение»).25Откуда получаем, что φ n = 5 Fn (1 + o(1) ) при n → ∞ ⇒ n = logφ Fn + O(1) . Тогда для затраталгоритма получаем: C E ( Fn+1 , Fn ) = n = logφ Fn + O(1) = Ω(log Fn ) . Следовательно, оценкаTE (a1 ) = O (log a1 ) точна. Более того, можно показать, что TE (a1 ) = Θ(log a1 ) .
Для этого1докажем, что TE (a1 ) > logφ a1 + γ .4⎡FF ⎤Рассмотрим систему вложенных сегментов Φ1 ⊃ Φ 2 ⊃ Φ 3 ⊃ ... , где Φ n = ⎢ 2 n , 2 n+1 ⎥ .⎣ F2 n−1 F2 n ⎦Φ1Φ2...1F2F12F4F3φF5F4F3F2Для чисел Фибоначчи справедливо равенство:Fn2 − Fn−1Fn+1 = (−1) n , n = 1,2,...которое легко устанавливается по индукции (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
