Чет про программирование / асимптотика

Доказательство. Пусть c — произвольная константа такая, что

0 < 2c ≤ cmin. Индукцией по n докажем, что Tmin(n) ≥ cn lg n для любого n ≥ 1. Действительно, базис индукции при n = 1 очевиден. Пусть n ≥ 2. Из алгоритма QuickSort получаем

T

min

(n)

≥

q

min

{

T

min

(q

−

1) + T

min

(n

−

q)

}

+ T ′

(n)

≥

{

1;:::;n

min

}

≥

q

min

{

T

min

(q

−

1) + T

min

(n

−

q)

}

+ 2c n.

{

1;:::;n

}

Случай 1. Минимум указанного выражения достигается при q = 1

или q = n. Рассмотрим функцию g(x) = x lg x на интервале (0, ∞).

Так как вторая производная g′′(x) > 0 положительна, функция g(x)

является выпуклой вниз 32. Поэтому

g(n) − g(n − 1) ≤ g′(n) = lg(en) ≤ n + 1.

Используя индукционное предположение, получаем

Tmin(n) ≥ Tmin(0) + Tmin(n − 1) + 2c n ≥

≥cg(n − 1) + 2c n ≥

≥cg(n) = cn lg n.

Случай 2. Пусть не выполняется случай 1. В доказательстве леммы 12 показано, что минимум функции fk(x) = x lg x+(k−x) lg(k−x) на интервале (0, k) есть значение fk(k/2) = g(k)−k. Используя индукционное предположение, получаем

Tmin(n) ≥

min

c(q

−

1) lg(q

−

1) + c(n

−

q) lg(n

−

q)

}

+ 2c n =

1<q<n{

=c min { fn−1(x) | 0 < x < n − 1 } + 2c n =

=c ( g(n − 1) − (n − 1) + 2n) ≥ cg(n) = cn lg n.

Таким образом, Tmin(n) = Ω(n lg n).

32 Функция g(x) называется выпуклой вниз на интервале (a; b), если для любого

x0 (a; b) касательная l(x) = g(x0) + g′(x0)(x − x0) лежит ниже графика функции,

т. е. l(x) ≤ g(x) для всех x (a; b).

101

Теперь покажем, что время порядка n lg n достигается при работе алгоритма быстрой сортировки33. Сначала для любого n ≥ 2 определим входную последовательность x1, . . . , xn такую, что при работе алгоритма быстрой сортировки после каждого вызова функции P artition(p, r)

процедура QuickSort применяется к двум подмассивам, один из которых xp, . . . , xq−1 имеет размер (r − p + 1)/2 , а другой xq+1, . . . , xr —

размер (r − p + 1)/2 − 1. Последовательность x1, . . . , xn с таким свойством будем называть сбалансированной.

Индукцией по n докажем, что любую последовательность из n различных элементов можно упорядочить так, что получится сбалансированная последовательность. Пусть z1 < . . . < zn — упорядочивание по возрастанию произвольной последовательности y1, . . . , yn различных элементов. Если n = 2, последовательность z1, z2 очевидно является сбалансированной. Пусть n > 2. Переставим элемент z n=2 +1 на последнее место, а последовательности z1, . . . , z n=2 и z n=2 +2, . . . , zn соответственно длины n/2 и n/2 − 1 упорядочим требуемым образом согласно индукционному предположению. Далее во второй полученной последовательности длины n/2 − 1 её последний элемент переместим на её первое место. Нетрудно понять, что построенная последовательность является сбалансированной.

Обозначим через T (n) максимальное время работы алгоритма быстрой сортировки на сбалансированных входных последовательностях размерности n. Индукцией по n докажем справедливость неравенства

T (n) ≤ c n lg n

для любого n ≥ 2, где c — фиксированная константа такая, что c ≥ max { cmax, T (2), T (3), T (4) }. Базис индукции при n = 2, 3, 4 очевиден. Пусть n ≥ 5. Тогда n/2 ≥ n/2 − 1 ≥ 2. Из алгоритма QuickSort и

33 Ввиду полученной в лемме 15 верхней оценки среднего времени Tave(n) =

O(n lg n) этого, вообще говоря, не требуется. Здесь мы строим пример входных данных, на которых достигается асимптотический порядок минимального времени.

102

индукционного предположения получаем

T (n)	≤	T (	n/2		) + T ( n/2	−	1) + T ′	(n) + 1	≤
							max

≤c n/2 lg n/2 + c( n/2 − 1) lg( n/2 − 1) + cn ≤

≤2 c n2 lg n2 + cn = cn lg n.

Следовательно, T (n) = O(n lg n). Поэтому алгоритм быстрой сортировки на любой сбалансированной входной последовательности требует времени порядка n lg n. Таким образом, минимальное время Tmin(n) есть

Θ(n lg n). Лемма 14 доказана.

Лемма 15. Среднее время Tave(n) работы алгоритма быстрой сортировки QuickSort есть Θ(n lg n).

Доказательство. При вызове процедуры QuickSort сначала происходит обращение к функции P artition, для которой потребуется не более, чем cmax n операций. Определяется позиция опорного элемента,

идалее снова с помощью алгоритма QuickSort сортируются две подпоследовательности, длины которых равны соответственно q − 1 и n − q, где 1 ≤ q ≤ n. Предполагая, что все входные данные равновероятны,

иоценивая ожидаемое время работы алгоритма QuickSort, нетрудно получить следующее неравенство:

1 ∑n

Tave(n) ≤ cmax n + n q=1( Tave(q − 1) + Tave(n − q) ).

Так как для любой функции h(q) справедливы равенства

n	n	n−1
∑q	∑	∑
h(q − 1) =	h(n − q) =	h(q),
=1	q=1	q=0

имеем следующую оценку среднего времени работы:

2 n∑−1

Tave(n) ≤ cmax n + n q=0 Tave(q).

103

Пусть c — произвольная константа такая, что c ≥ max { 2 cmax, Tave(0)+

Tave(1) }. Докажем справедливость неравенства Tave(n) ≤ cn lg n для любого n ≥ 2. При n = 2 имеем

Tave(2) ≤ 2 cmax + Tave(0) + Tave(1) ≤ 2 c lg 2.

В примере 1 (viii) мы доказали неравенство

n−1	n2		n2
∑q
q ln q ≤	2	ln n −	4	− ln 4 + 1.
=2

Используя индукционное предположение, при n ≥ 3 получаем

1		2		2			n−1
							∑q
Tave(n) ≤	2	cn +	n	( Tave(0) + Tave(1) ) +	n	c	q lg q ≤
							=2

≤

1

2

2

c lg e (

n2

ln n −

n2

cn +

c +

2

n

n

2

4

c (

1

2

n

2

lg e ) + cn

=

n

−

−

lg e +

2

n

2

n

≤cn lg n.

)

− 2 ln 2 + 1 = lg n ≤

Таким образом, Tave(n) = O(n lg n). Учитывая лемму 14, получаем

Tave(n) = Θ(n lg n). Лемма 15 доказана.

Непосредственно из лемм 13–15 вытекает следующая теорема.

Теорема 14. Минимальное и среднее время работы алгоритма быстрой сортировки есть Θ(n lg n), максимальное время равно Θ(n2).

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

Θ(n2). В отличие от других рассмотренных методов сортировки, алгоритм QuickSort быстрой сортировки "предпочитает" неупорядоченные входные данные. Несмотря на такую медленную работу в наихудшем случае, этот алгоритм часто оказывается предпочтительнее, особенно 104

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

Дальнейшее улучшение алгоритма быстрой сортировки связано с более аккуратным выбором опорного элемента в функции P artition, например, случайным образом или как медиану трёх случайно определенных элементов массива. В этом случае получаем рандомизированную версию быстрой сортировки. Такой подход ускоряет время работы за счёт уменьшения константы в выражении Θ(n lg n).

6.Алгоритм пирамидальной сортировки и оценки его трудоёмкости

При сортировке n-элементной входной последовательности алгоритм пирамидальной сортировки34 требует времени работы в худшем и в среднем случае Θ(n lg n) и, следовательно, является оптимальным в классе алгоритмов сортировки сравнением. При этом сортировка входной последовательности осуществляется на месте и не требует дополнительной памяти. Алгоритм использует структуру данных, называемую пирамидой. Познакомимся с этим понятием.

Рассмотрим произвольный массив A = (a1, . . . , an) размерности n. Свяжем с массивом A бинарное дерево DA, определяемое следующим образом. Каждая вершина дерева DA соответствует элементу массива

A. В корне дерева находится элемент a1. Для любого i = 1, 2, . . . , n/2

вершина ai имеет двух сыновей a2i и a2i+1, за исключением случая, когда n чётно и i = n/2 . При этом a2i и a2i+1 являются левым и правым сыном и располагаются под вершиной ai слева и справа соответственно. Если n чётно, вершина an=2 имеет единственного сына an. Другие вершины дерева DA не имеют сыновей. Пример такого бинарного дерева

DA для массива A = (7, 4, 3, 9, 8, 6, 1, 10) представлен на рис. 6.

34 Пирамидальная сортировка была открыта J. W. J. Williams. Эффективный под-

ход к построению пирамиды предложил R. W. Floid.

105

Рис. 6. Бинарное дерево DA для массива A

Мы получили представление произвольного массива A бинарным де-

ревом DA. Заметим, что это дерево обладает следующими свойствами:

•на всех уровнях35, кроме, быть может, последнего, дерево полностью заполнено. Иными словами, каждая вершина глубины меньшей, чем h − 1 имеет ровно двух сыновей, где h — высота дерева;

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

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

кправому сыну. Такая нумерация соответствует нумерации элементов массива A в порядке возрастания его индексов. Поэтому можно отождествлять массив A и бинарное дерево DA.

Пирамида — это структура данных, представляющая собой массив, который рассматривается как бинарное дерево, определённое выше и

35 Вершины дерева, имеющие одинаковую глубину, образуют один уровень. Все

уровни занумерованы в соответствии со значением глубины их вершин.

106

дополнительно обладающее следующим свойством убывания:

ai ≥ a2i, i = 1, . . . , n/2 ,

aj ≥ a2j+1, j = 1, . . . , (n − 1)/2 .

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

Не каждый массив является пирамидой. Например, для массива

A = (7, 4, 3, 9, 8, 6, 1, 10) нарушается условие a5 ≤ a2 (см. рис. 1). Однако каждый массив A = (a1, . . . , an) можно преобразовать в массив, состоящий из тех же элементов и являющийся пирамидой36. Действительно, в дереве DA элементы a n=2 +1, . . . , an — концевые вершины, а все вершины a1, . . . , a n=2 имеют сыновей. Перестроение массива A проведём снизу вверх. Начиная с последней родительской вершины a n=2

и заканчивая корнем a1, проверяем, выполняется ли для текущей рассматриваемой вершины с индексом i свойство убывания: ai ≥ a2i и ai ≥ a2i+1 (последнее неравенство нужно проверять, когда 2i + 1 ≤ n). Если это свойство не выполнено, элемент ai следует поменять с б´ольшим из её сыновей a2i, a2i+1. Для этого в переменную largest записываем индекс наибольшего из элементов ai, a2i, a2i+1. Если largest = i, то ai

уже погрузился до нужного места, иначе меняем местами элементы ai

и alargest. Далее начинаем проверку свойства убывания для элемента alargest, находящегося на следующем уровне, и так до тех пор, пока элемент ai не погрузится до нужного места в дереве DA. Погружение вершины с индексом i оформим процедурой P ushdown с параметрами pushingnumber — индекс элемента массива, погружаемого вниз до правильной позиции, и heapsize — размерность рассматриваемого массива

36 Далее предполагаем n ≥ 2, так как одноэлементный массив является пирамидой.

107

A (в дальнейшем мы будем уменьшать размерность пирамиды). Сам алгоритм построения пирамиды оформим процедурой BuildHeap.

Procedure P ushdown(pushingnumber, heapsize); i := pushingnumber;

while i ≤ heapsize/2 do begin

l := 2i;

r := 2i + 1;

if al > ai then largest := l else largest := i;

if (r ≤ heapsize) and (ar > alargest) then largest := r; if largest = i then i := heapsize

else begin

Swap(ai, alargest);

i := largest end

end.

Procedure BuildHeap(heapsize);

for i = heapsize/2 downto 1 do P ushdown(i, heapsize).

Пример 13. На рис. 7 показано построение пирамиды процедурой

BuildHeap для массива A с бинарным деревом DA, изображённым на рис. 6. Здесь приведено дерево DA для текущего состояния массива A

после выполнения процедуры P ushdown(i, 8), i = 4, 3, 2, 1.

Лемма 16. Пусть T (n) — время работы алгоритма P ushdown(i, n)

и k — высота вершины ai в дереве DA. Тогда существует такая положительная константа c, не зависящая от i, n и входного массива A

размерности n, что T (n) ≤ ck ≤ c lg n для любого n ≥ 2.

108

Рис. 7. Построение пирамиды

Доказательство. Пусть h — высота бинарного дерева DA. Так как каждая вершина дерева DA глубины меньшей, чем h−1 имеет ровно два сына, h = lg n по лемме 11. Поэтому k ≤ h ≤ lg n. Осталось заметить, что каждая итерация while-цикла означает спуск по дереву DA на один уровень. Лемма 16 доказана.

Лемма 17. Минимальное, среднее и максимальное время работы алгоритма BuildHeap(n) есть Θ(n).

Доказательство. Пусть h — высота бинарного дерева DA, соответствующего массиву A размерности n. Время работы процедуры

P ushdown(i, n) зависит от высоты k вершины с индексом i и не превосходит ck операций, где c — константа, определённая в лемме 16. Причём k ≤ h и число вершин высоты k в бинарном дереве DA не превосходит

2h−k по лемме 10(i). Кроме того, n ≥ 2h в силу леммы 11. Таким об109

разом, для времени T (n) работы алгоритма BuildHeap(n) при n ≥ 2

выполняются следующие оценки

		h		h	k
		∑		∑
T (n)	≤	2h−k ck = c2h				≤
		k=0		k=0	2k
		∞	k
		∑
	≤ cn		2k	= 2cn = O(n),
		k=0

здесь при q = 1/2 мы воспользовались равенством37

∞		q
∑		−
kqk =				.
(1			q)2

k=0

В алгоритме BuildHeap(n) число вызовов процедуры P ushdown(i, n)

равно n/2 . Поэтому T (n) = Ω(n). Лемма 17 доказана.

Рассмотрим алгоритм пирамидальной сортировки. Требуется отсортировать элементы массива A = (a1, . . . , an) в порядке возрастания. С помощью процедуры BuildHeap(n) массив A преобразуем в пирамиду. Ввиду свойства убывания пирамиды наибольший элемент массива будет находиться в корне пирамиды a1. Обменяем местами элементы a1

и an. В результате наибольший элемент массива A займёт требуемую позицию. Перейдём к массиву меньшей размерности a1, . . . , an−1, который также преобразуем в пирамиду. Заметим, что свойство убывания сохранится для всех вершин с индексом i при i = 2, . . . , n − 1 и может нарушиться только для нового корневого элемента a1. Поэтому для получения пирамиды достаточно лишь погрузить элемент a1 до нужного места с помощью процедуры Pushdown(1, n − 1). После этого массив A

на первых n − 1 позициях превратится в пирамиду. Снова обменяем элементы a1, an−1 и перейдём к массиву размерности n − 2. Продолжаем описанный процесс до тех пор, пока не дойдём до одноэлементного массива a1. Программная реализация этого алгоритма приведена в следующем псевдокоде.

37 Это равенство получается дифференцированием суммы геометрической про-

	k∑		1
грессии	∞ qk =	(1	q)	и умножением на q при условии −1 < q < 1.
	=0		−
			110