С.А. Абрамов - Вычислительная сложность алгоритмов, страница 3

придётся произвести сравнение каждогоэлемента с каждым в случае, если изначальный массив упорядочен. Найдём сложность всреднем TQS (n) алгоритма быстрой сортировки. Для этого введём случайную величину ξ n (a) ,отражающую общее число сравнений, необходимых алгоритму для упорядоченияперестановки a.

Не трудно видеть, что TQS (n) в этом случае будет выражаться формулойTQS (n) = Eξ n =1∑ ξ n (a) .n! a∈Π nРазложим пространство Π n следующим образом: Π n = K n1 + ... + K nn , где события K niзаключаются в том, что разбивающий элемент после разбиения занимает i-ю позицию. Таккак в качестве разбивающего элемента всегда берём первый, то события 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 .