Архив WinRAR / Книги, блеать / Абрамов С.А. Вычислительная сложность алгоритмов (конспект лекций)

Рассмотрим множество всевозможных перестановок их n элементов Πn , оно же будет являться вероятностным пространством, с вероятностью каждого элемента n1! (т.к.

количество всевозможных перестановок из n элементов равно n!).

Для дальнейшего нам понадобится факт из теории вероятностей, получивший название

формула полного математического ожидания.

Пусть пространство событий W может быть разложено на сумму попарно несовместных

событий	Wi: W =W1 + ... +Wl , Wi ∩Wj = при i ≠ j . Пусть ξ								— случайная величина,
определённая на W. Тогда по определению Eξ = ∑ξ(ω)P(ω) . Пусть известны условные
математические ожидания E(ξ | Wk ), k =1, ... , l .						ω W
						Тогда формула полного математического
ожидания выглядит следующим образом:
	Eξ = ∑l	E(ξ		Wk )P(Wk ).
	k=1
Утверждение.
(i)	Пусть 1 ≤ u ≤ n , 1 ≤ v ≤ n и событие					F u,v заключается			в том,	что v-й	элемент
						n
	перестановки a1,..., an равен u, т.е.				av = u . Тогда вероятность					такого	события
	Pn (Fnu,v )= 1 .
	n
(ii)	Пусть 1 ≤ u ≤ n и p — некоторая перестановка чисел 1, ... , u −1 . Пусть событие
	Gu, p заключается в том, что порядок элементов, меньших u, совпадает с p. Тогда
	n
	вероятность такого события Pn (Gnu, p )=					1		.
						(u −1)!
(iii)	Пусть 0 < u < v ≤ n и событие Hnu,v заключается в том,								что существует ровно u
	элементов перестановки a1, ... , an , для которых верно ai < av									1 ≤ i < v . Тогда
	вероятность такого события Pn (Hnu,v )=				1 .
						v

Доказательство:

(i)очевидно: всего перестановок n! , перестановок, у которых один элемент фиксирован (n −1)! Pn (Fnu,v )= (n n−!1)! = n((nn−−11)!)! = 1n .

(ii)всего перестановок n! , из них перестановок, в которых порядок элементов

	меньших	u фиксирован, Cnu−1(n −u +1)!=			n!(n −u +1)!		=	n!		, откуда
					(u −1)!(n −u +1)!			(u −1)!
	Pn (Gnu, p )=	1		.
		(u −1)!

(iii)если p — некоторая перестановка 1, ... , v , то число перестановок (a1, ... , an ) Πn ,

для которых ψn (a1, ... , av ) = p , равно Cnv (n −v)!= nv!! . Число перестановок p, для

11

которых последний элемент равен u −1, составляет (v −1)!, откуда общее число событий равно nv! Pn (Hnu,v )= 1v .

Сортировка простыми вставками (I1).

упорядочены

678

На i-й итерации алгоритма первые i элементов массива упорядочены: x1,..., xi , xi+1,... и требуется поставить на место xi+1 . Для этого xi+1 сравнивается подряд со всеми элементами слева, начиная с xi , до тех пор, пока не будет найден элемент, меньший xi+1 , или не будет достигнута граница массива. После определения правильного места для элемента xi+1 начинаются обмены элемента xi+1 с элементом, стоящим справа до тех пор, пока элемент xi+1 не встанет на место.

Найдём сложность в среднем этого алгоритма. Для этого введём следующие случайные величины ξn1,...,ξnn−1 такие, что a Πn ξni (a) показывает затраты на i-м шаге алгоритма.

Тогда TI1 (n) = E(ξn1 +... +ξnn−1 )= Eξn1 +... +Eξnn−1 . Рассмотрим события Hnk ,i+1 , k = 0,1,...,i , тогда

Πn = Hn0,i+1 + Hn1,i+1 +... + Hni,i+1 .

По формуле полного математического ожидания получаем:

Eξni =

1

∑i

E(ξni

Hnk ,i+1 ).

i

+

Допустим, что событие Hnk ,i+1

1 k=0

выполнено, тогда

ξni (a) =

i −k +1, k > 0

k = 0

i,

i

i

k ,i+1

i

1

i

i

1

ξn (a) = E(ξn

Hn

)

Eξn

=

i +

∑(i −k +1) =

+1

−

i +

i

+1

1

k=1

2

n−1

i

1

n−1

i

1

Откуда

получаем TI1 (n) = ∑

+1−

= n −

1+∑

−

. Из курса математического

i +1

i

+

1

i=1

2

i=1

2

n

анализа известно, что ∑1

1 (n)

получаем:

= ln n +O(1) , тогда для TI

i=1 i

(n +

4)(n −1)

n2

T (n) =

−ln n +O(1)

=

+O(n) .

I

4

4

1

По числу перемещений (обменов) оценка останется верной, т.к. число перемещений отличается от числа сравнений не более, чем на 1.

Пусть ξ — затраты на сравнения, а η — затраты на перемещения. Тогда суммарная сложность в среднем будет равна: E(ξ +η)= Eξ +Eη .

Сортировка «пузырьком».

Имеется массив x1, x2 ,..., xn , который требуется отсортировать. Сравниваем парами xi и xi+1 ,

если xi > xi+1 ,	то меняем их местами и продолжаем с xi+1 . После первого прохода последний
(наибольший)	элемент окажется на своем месте. Второй проход идёт до n −1 , третий до
	12

n −2 и т.д. Заканчиваем, когда ни одной перестановки не было или остался массив из одного элемента.

Сложность в среднем такого алгоритма составит T (n) = n −	π n .
	2

Быстрая сортировка (QS = quick sort).

Есть массив x1, x2 ,..., xn , который нужно отсортировать. Для этого выбираем разбивающий

элемент (не важно какой, например, первый). Разбиваем элементы массива на 2 группы: те элементы, которые меньше разбивающего, и те, которые больше. Далее применяем ту же процедуру рекурсивно к полученным после разбиения двум частям.

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

TQS (n) = Eξn = 1 ∑ξn (a) . n!a Πn

Разложим пространство Πn следующим образом: Πn = Kn1 +... + Knn , где события Kni заключаются в том, что разбивающий элемент после разбиения занимает i-ю позицию. Так

как в качестве разбивающего элемента всегда берём первый, то события	Kni будут
совпадать с событиями Fni,1 , откуда Pn (Kni )= Pn (Fni,1 )= 1 , i =1,..., n . После	разбиения
n
исходная перестановка a разбивается на a′ и a′′, причём a′ Πi−1 , a′′ Πn−i .

Введём случайные величины ξn′(a) = ξi−1(a′)

и ξn′′(a) = ξn−i (a′′) ,

тем самым мы останемся в

том же вероятностном пространстве.

n

n

}

на разбиение

TQS (n) = Eξn = ∑E(ξn

Kni )Pn (Kni )= ∑

n −1 +E(ξn′

Kni )+E(ξn′′

Kni )

1

=

i=1

i=1

n

Kni )]

= n −1+

1 ∑n [E(ξn′

Kni )+E(ξn′′

n i=1

Используя очевидный факт Kni =				∑Gni, p , получаем:
				p Πi−1
E(ξ′				K i	)=		∑	ξ − ( p)		1
n				n				i 1		(i −1)!
							p Πi−1
E(ξn′′		Kni )= ∑ ξn−i ( p)								1
										(n −i)!
					1		p Πn−i
							n
Откуда получаем Eξn = n −		1+				∑(Eξi−1 +Eξn−i ) .
					n	i=1

=Eξi−1 ,

=Eξn−i .

Непосредственной проверкой

n	n	n−1			2	n−1
устанавливается, что ∑Eξi−1 = ∑Eξn−i = ∑Eξk				TQS (n) = Eξn = n −1+		∑Eξk , что
i=1	i=1	k=0			n k =0

можно переписать в следующем виде:

13

TQS (n) = n −1+ 2

n−1

(*)

∑TQS (k) ,

n k=0

(для упорядочения массива нулевой длины не

причём, как не трудно видеть, TQS (0) = 0

требуется ни одного сравнения). Тогда, для n ≥1, получаем

n−2

2 ∑TQS (k) .

(**)

TQS (n −1) = n −2 +

n k=0

Домножим (*) на n и вычтем (**), умноженное на (n −1) , тогда получим:

(n −1)

nT

(n) − (n −1)T (n −1) = n(n −1) − (n −1)(n − 2) + 2T

QS

QS

1444244443

QS

2(n−1)

nTQS (n) −(n +1)TQS (n −1) = 2(n −1)

2(n −1)

TQS (n)

−

TQS (n −1)

=

.

n +1

n

n(n +1)

Введём обозначение

t(n) =

TQS (n)

, тогда

предыдущее

равенство перепишется

в

виде:

2(n −1)

n +1

t(n) −t(n −1) =

, причём t(0) = 0 .

Известно,

что если t(n) −t(n −1) =ϕ(n)

для

всех

n(n +1)

n

n ≥ n0 , тогда t(n) = ϕ(n0 ) + ∑ϕ(k)

(доказывается по индукции)

для t(n) получаем:

k=n0 +1

n

k −1

n

1

n

1

t(n) = 2∑

= 2∑

−2∑

.

k(k +1)

k +1

k(k +1)

k=1

k=1

k=1

Для первого ряда из математического анализа известна оценка: ∑n 1 = ln n +O(1) , второй ряд

i=1 i

сходится, а значит, может быть оценён через O(1) , в итоге получаем:

t(n) = 2(ln n +O(1))−O(1) = 2ln n +O(1) TQS (n) = 2nln n +O(n) .

Получилась довольно приятная оценка, хоть и с участием логарифма. Но, как говорил Ландау, «Курица не птица, логарифм не бесконечность».

Для пространственной сложности верно SQS (n) = SQS (n) = O(1) .

Рассмотрим пространственные затраты стека: т.к. алгоритм работает с отложенными задачами, то для его реализации потребуется стек, в который будут помещаться пары ( p, q)

— сегменты массива, которые необходимо сортировать. Оказывается (что будет доказано ниже), что если из двух получающихся после разбиения частей для обработки брать меньшую, откладывая бόльшую, то затраты не превзойдут log2 n .

Утверждение. Если бинарная рекурсивная сортировка такова, что после разбиения для сортировки выбирается меньшая часть, то количество отложенных в стеке задач не превзойдёт log2 n .

14

Доказательство: после разбиения длина короткого массива ≤ n

,

при этом длинна длинного

2

n

≤ n −1 . Пусть x

′

— меньшая часть, длина которой равна

′

≤

, x

′′

— большая, длинной

n

2

′′

сортировки выбираем x

′

,

x

′′

откладывая

в

стек,

тогда в стек попадёт

n ≤ n −1 . Для

max{log2 n′+1, log2 n′′}≤ log2 n , что и требовалось доказать.

Приведём алгоритм быстрой сортировки на псевдокоде:

qsort(k,l): if k<l–1 then

xk выбирается в качестве разбивающего элемента, и выполняется разбиение 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)

fi

fi

Рандомизированные алгоритмы.

Рассмотрим функцию random(N), возвращающую случайное число от 0 до N −1 , с

вероятностью выпадения каждого N1 . Введём элемент рандомизации в алгоритм быстрой сортировки, тогда на псевдокоде он перепишется следующим образом:

qsort(k,l): if k<l–1 then

m:=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)

fi

fi

Дадим другую формулировку алгоритма быстрой сортировки:

Пусть имеется полоска клетчатой бумаги размером 1×n клеток, которую требуется разрезать на отдельные клетки. Разрезать может только специальный разрезальщик, причем за одну операцию он может вырезать одну любую клетку (с края или из середины). При вырезании клетки из середины полоска разбивается на две. За одно отрезание разрезальщик берёт (n −1) рубль, где n — длинна полоски, из которой вырезается клетка. Цель —

порезать всю полоску на клетки.

В такой формулировке сложностью алгоритма является суммарное количество рублей, необходимых для работы разрезальщику.

Сценарий для разрезаний удобно изобразить в виде двоичного дерева. Для n = 3 (полоска из 3-х клеток) получаем следующие варианты сценариев (3-сценарии):

	3			3	3		3		3
	0	2	0	2		2	0	2	0
	0	1	1	1		1	1	1	0
				0		0
					15

Смежные вершины здесь обозначены числами, соответствующими количествам остающихся клеток с одной и другой стороны, после того как одна из исходных будет вырезана.

Любой n-сценарий получается из левого (i −1) -сценария и правого (n −i) -сценария:

	n
i − 1	n − i

Обозначим через Sn множество всех n-сценариев. При фиксированном n всем n-сценариям приписываются следующие вероятности:

−

если n = 0 или n =1, то Pn (s) =1;

1

−

если n >1, то Pn (s) = n Pi−1(s′)Pn−i (s′′) .

Покажем,

что так

введённая

вероятность

удовлетворяет

условию ∑Pn (s) =1 .

s Sn

Доказательство проведём по индукции:

для

n = 0

и

n =1

утверждение

верно

по

определению; пусть

для

всех для k < n

выполнено

∑Pk (s) =1 , покажем

что для

n

s Sk

утверждение тоже верно:

n

1 Pi−1(s′)Pn−i (s′′) =

∑Pn (s) ={поопределению} = ∑ ∑

s S

n

i=1 s′ S

i−1

n

′′

s Sn−i

1

n

1

n

=

∑

∑Pi

−1(s′)

∑Pn−i (s′′)

=

∑1 1 =1.

n i=1

s′ Si−1

s′′ Sn−i

n

i=1

14243 1442443

=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)	. Разложим
вероятностное пространство Sn	следующим образом: Sn = Sn1 +...+ Snn , где Sni	соответствует

тому, что левый сценарий является (i −1) -сценарий, а правый — (n −i) -сценарий. Не трудно

проверить, что

P

(Si ) = 1 , откуда получаем:

n

n

n

n

n

Sni )]= n −1+

n

Eχn = ∑E(χn

Sni

) 1 = n −1

+ 1

∑[E(χn′

Sni )+E(χn′′

1 ∑(Eχi−1 +Eχn−i )=

i=1

n

n

i=1

n

n−1

n i=1

= n −1+

2

∑Eχn−i = n −1+ 2 ∑Eχk

n

i=1

n k=0

т.е. получаем, что Eχn

= n −1+ 2

n−1

= 0 . Откуда, аналогично предыдущему случаю,

∑Eχk , Eχ0

~

n k=0

(n) = Eχn = 2nln n

+O(n) . В

итоге получилось,

что введение элемента

получаем: TQS

рандомизации никак не отразилось на сложности в среднем алгоритма быстрой сортировки.

16

Способы ускорения алгоритма быстрой сортировки.

Если на каждой итерации выбирать 3 случайных элемента и брать серединный в качестве разбивающего, то в итоге сложность в среднем так модифицированного алгоритма составит

127 nln n +O(n) .

Алгоритм Евклида (E).

Рассмотрим алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух целых положительных чисел a0 ≥ a1 , которые будут являться входом алгоритма. Алгоритм

заключается в последовательных делениях с остатком:

a0 = q1a1 + a2 a1 = q2a2 + a3

...

an−3 = qn−2an−2 + an−1 an−2 = qn−1an−1 + an an−1 = qnan

Тогда an будет являться НОД, что легко показать по индукции:

НОД(a0 , a1) = НОД(a1, a2 ) = ... = НОД(an ,0) = an .

Затраты алгоритма будем определять числом необходимых делений с остатком CE (a0 , a1) .

Не трудно видеть, что CE (a0 , a1) ≤ a1 , т.к. после первого деления остаток остаётся меньше a1 ,

а при каждом следующем делении остаток будет меньше предыдущего как минимум на 1. В связи с этим в качестве входа можно взять только второе меньшее число a1 , тогда TE (a1) ≤ a1 .

Один шаг алгоритма Евклида переводит пару ai−1, ai в пару ai , ai+1 . Для оценки количества

шагов алгоритма Евклида, которое совпадает с количеством необходимых делений с остатком, хорошо было бы найти такую функцию λ(ai−1, ai ) , для которой выполнялись бы

следующие условия:

1.λ(ai−1, ai ) ≥ 0 ;

2.CE (ai−1, ai ) ≤ λ(ai−1, ai ) ;

3.на каждом шаге алгоритма Евклида она уменьшается хотя бы на 1.

Рассмотрим функцию λ(k,l) =ν(k) +ν(l) −2 , где ν(x) соответствует битовой длине x .

Очевидно, что она удовлетворяет первым двум сформулированным условиям. Убедимся в справедливости третьего. Справедливо следующее

Утверждение. Пусть k,l N , k > l , r — остаток от деления kl . Тогда

1.ν(k) >ν(r) ;

2.λ(k,l) > λ(l, r) .

Доказательство:

1. k = ql + r , q ≥1 k ≥ l + r > 2r ν(k) >ν(l) ;

17

2.ν(k) >ν(r) ν(k) +ν(l) −2 >ν(l) +ν(r) −2 λ(k,l) > λ(l, r) , что и требовалось доказать.

CE (a0 ,a1) ≤ λ(a0 , a1) =ν(a0 ) +ν(a1) −2

CE (a0 , a1) = CE (a1, a2 ) +1 ≤ν(a1) +ν(a2 ) −1 ≤ 2ν(a1) −1

123

≤ν (a1 )

TE (a1 ) = max CE (a0 , a1) ≤ 2ν(a1) −1 = 2 log2 a1 +1

a0 ≥a1

Итак, для сложности алгоритма Евклида была получена оценка: TE (a1) = O(log a1) . Возникает вопрос: можем ли мы улучшить эту оценку? Ответ: нет, эта оценка точная. Для доказательства точности оценки построим последовательность входов (a0(1) , a1(1) ), (a0(2) ,a1(2) ), (a0(3) , a1(3) ), … такую, что для неё будет выполняться CE (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 делений: CE (Fn+1, Fn )= n . Используем формулу Бене:

Fn =

1

(φn

−(−φ)−n ), где φ =

1+

5 =1,61803... («золотое сечение»).

5

2

Откуда получаем, что φn =

5F (1+o(1))

при n → ∞ n = log

φ

F +O(1) . Тогда для затрат

n

n

алгоритма получаем:

CE (Fn+1, Fn ) = n = logφ Fn +O(1) = Ω(log Fn )

. Следовательно,

оценка

TE (a1) = O(log a1)

точна. Более того, можно

показать,

что TE (a1 ) = Θ(log a1) . Для

этого

докажем, что T (a ) > 1 log

φ

a +γ .

E

1

4

1

F2n

F2n+1

Рассмотрим систему вложенных сегментов Φ1 Φ2 Φ3

... , где Φn =

,

.

F

F

2n−1

2n

Φ1

Φ2

1

...

2

F2

F4

φ

F5

F3

F1

F3

F4

F2

Для чисел Фибоначчи справедливо равенство:

Fn2 − Fn−1Fn+1 = (−1)n , n =1,2,...

которое легко устанавливается по индукции (см. задачу 24). Используя это равенство, для длины сегмента Φn получаем выражение:

	Φ		=	F	−	F	=	F F	− F 2	=	1
		n		2n+1		2n		2n+1 2n−1	2n
				F2n		F2n−1		F2n F2n−1			F2n F2n−1

18

Так как

Φ

n

→ 0 при n → ∞ ,

a >1 N : n ≤ N выполняется

1

≤

Φ

n

=

1

, а для

1

a1

F2n F2n−1

N +1 неравенство

уже

не

выполняется, т.е.

1

>

Φ

N +1

=

1

a < F

F

+2

.

a1

F2 N +1F2 N +2

1

2 N +1 2 N

Используем формулу Бене и получим:

a1 < F2N +1F2 N +2 =

1 (φ2 N +1

−(−φ)−2 N −1 )

1

(φ2 N +2 −(−φ)−2 N −2 )< cφ4 N

5

5

N > 1 log

a −log

φ

c , что доказывает оценку T (a ) = Θ(log a ) . Для сложности в среднем

4

φ 1

E

1

1

12ln 2

(a ) =

ln a +O(1) .

можно получить оценку T

E

1

π 2

1

Расширенный алгоритм Евклида (EE).

Можно показать, что s,t Z : sa0 +ta1 = НОД(a0 , a1 ) .

В частности,

если a0

и a1

взаимно

простые, то s,t Z : sa0 +ta1 =1.

Пусть в алгоритме Евклида уже найдены a0 , a1,...,ai

, 1 ≤ i ≤ n −1 и пусть найдены s0 ,t0 ;

s1,t1 ; … ; si ,ti	такие, что s0a0 +t0a1 = a0 ; s1a0 +t1a1 = a1	; … ; si−1a0 +ti−1a1 = ai−1 ; sia0 +tia1 = ai .
ai−1 = qiai + ai+1	ai+1 = ai−1 −qiai = si−1a0 +ti−1a1 −qi (sia0	+tia1 ) = (si−1 −qi si )a0	+(ti−1 −qiti )a1 , т.е.
		14243	14243
		si+1	ti+1
si+1 = si−1 −qi si ; ti+1 = ti−1 −qiti , при этом s0 =1, t0 = 0 , s1		= 0 , t1 =1.

Пример. a0 = 39; a1 =15

Остатки, получаемые алгоритмом Евклида: 9, 6, 3, 0. s, t: 1,-2; -1,-3; 2,-5; 2 39 +(−5) 15 = 3 = НОД(39,15) .

Алгоритм Евклида, в котором дополнительно определяются числа ti , si буден называть

расширенным алгоритмом Евклида (EE). Не трудно видеть, что для его сложности справедлива оценка: ёTEE (a1 ) < 6log2 a1 +3 , т.е. всё утроилось.

Можно также найти числа sn+1,tn+1 : sn+1a0 +tn+1a1 = 0 (для примера, рассмотренного выше,

sn+1 = s5 = −5; t5 =13 ).

Для чисел

si , ti можно доказать

следующий факт:

s1

<

s2

< ... <

sn+1

,

t1

<

t2

< ... <

tn+1

.

Кроме того,

sn+1

=

a1

,

tn+1

=

a0

, тогда

sk

< a1,

tk

< a0 , k =1,2,..., n .

НОД(a ,a )

НОД(a , a )

0

1

0

1

Бинарный поиск (BS = binary search).

Есть массив x1,..., xn , элементы которого упорядочены по возрастанию. И есть ещё один

элемент y, для которого нужно найти место в этом массиве такое, что после вставки элемента y полученный массив был упорядоченным. Существуют следующие варианты для вставки y:

y ≤x ,	x	< y ≤ x	,	x	2	< y ≤ x , ... x	n−1	< y ≤ x	,	x	n	< y
1 1	1	2				3		n				n+1
		2				3		n

Задачей алгоритма является выдача числа от 1 до n +1 , соответствующего варианту правильного расположения y.

19

На псевдокоде алгоритм выглядит следующим образом: p:=1; q:=n-1;

while p<q do

p + q r:= 2 ;

if xr<y then p:=r+1 else q:=r fi

od

Не трудно видеть, что каждый шаг алгоритма переводит рассматриваемую задачу для

массива длины	k к задаче для массива длинны	k		или	k		−1	. Введём функцию
	2				2

λ(k) =ν(k) , тогда на каждом шаге алгоритма λ(k) будет убывать хотя бы на 1. Если y ≤ x1 ,

то λ(n) = log2 n +1 = TBS (n) = log2 (n +1) .

Сортировка бинарными вставками.

Рассмотрим алгоритм сортировки массива, основанный на алгоритме бинарного поиска. Алгоритм заключается в следующем: создается новый массив, который формируется из элементов исходного, каждый новый элемент занимает место, определяемое алгоритмом бинарного поиска. Тем сам на i-м шаге уже имеется упорядоченный массив из i −1 элемента, в который вставляется i-й элемент исходного массива.

n−1	n	n
Для сложности в худшем случае имеем: TB (n) = ∑ log2 (l +1) = ∑ log2 k		= ∑log2 n +O(1) .
l=0	k=1	k=1
Из курса математического анализа известна формула Стирлинга: n!= nne−n		2πn(1+o(1))

n

∑log2 n = log2 n!= nlog2 n +O(n) TB (n) = nlog2 n +O(n) .

k=1

Сортировка фон Неймана (vN).

Имеется массив x1,..., xn , который требуется упорядочить. Пусть на каком-то шаге алгоритма

массив разбивается на некоторое число упорядоченных сегментов. Тогда на следующем шаге сегменты объединяются парами и элементы внутри новых сегментов упорядочиваются. Далее опять происходит слияние сегментов по два и т.д. Причём для слияния сегментов используется вспомогательный массив такой же длины, что и исходный. Схематично действие алгоритма можно изобразить следующим образом:

При слиянии сегментов используется информация о том, что каждый из сливаемых сегментов сам по себе уже упорядочен, поэтому для слияния и одновременного упорядочивания двух сегментов длины k необходимо менее 2k операций сравнения, т.к. новый сегмент длины 2k формируется в новом массиве (новый сегмент формируется поэлементно из меньшего из наименьших нерассмотренных элементов исходных сегментов). На первом шаге исходный массив делится на сегменты длины 2 (за исключением, быть может, одного сегмента длины 1 в случае, если исходный массив имеет нечётное количество элементов), на втором шаге — длины 4 (если не было парного какому-то сегменту, то ещё не более одного сегмента длины 1, 2 или 3) и т.д. Таким образом, число этапов (перебросок) в сортировке фон Неймана будет равно log2 n . Т.к. число присваиваний на каждом этапе

20