Рефераты. Информатика. Текстовый редактор

Чтобы можно было рассуждать о среднем времени работы алгоритма, мы должны договориться о вероятностном распределе-нии входов. Для сортировки естественно допустить, что мы и сде-лаем, что любая перестановка упорядочиваемой последовательности равновероятна в качестве входа. При таком допущении уже можно оценить снизу среднее число сравнений, необходимых для упорядо-чения последовательности из n элементов.

Общий метод состоит в том, чтобы поставить в соответствие каж-дому листу v дерева решений вероятность быть достигнутым при данном входе. Зная распределение вероятностей на входах, можно найти вероятности, поставленные в соответствие листьям. Таким образом, можно определить среднее число сравнений, производи-мых данным алгоритмом сортировки, если вычислить сумму взятую по всем листьям дерева решений данного алгоритма, в ко-торой рi -- вероятность достижения i-го листа, а d, - его глубина. Это число называется средней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы 3.4.

Теорема 3.7. В предположении, что все перестановки п-элементной последовательности появляются на входе с равными вероят-ностями, любое дерево решений, упорядочивающее последователь-ность из п элементов, имеет среднюю глубину не менее log n!.

Доказательство. Обозначим через D (Т) сумму глубин листьев двоичного дерева Т. Пусть D (Т) -- ее наименьшее значение, взятое по всем двоичным деревьям Т с m листьями. Покажем индук-цией по m, что D(m)m log m.

Базис, т. е. случай /п=1, тривиален. Допустим, что предположе-ние индукции верно для всех значений m, меньших k. Рассмотрим дерево решений Т с и листьями. Оно состоит из корня с левым подде-ревом Т с k листьями и правым поддеревом T с k - 1 листьями при некотором i, 1ik. Ясно, что

D(T)=i+D(T)+(k-i)+D(T)

Поэтому наименьшее значение D (Т) дается равенством

D(k)= [k+D(i)+D(k-1)]. (3.1)

Учитывая предположение индукции, получаем отсюда

D(k)k+[i log i+(k-i)log(k-i)] (3.2)

Легко показать, что этот минимум достигается при i=k/2. Сле-довательно, D(k)k+k log =k log k

Таким образом, D (m)m log m для всех m1.

Теперь мы утверждаем, что дерево решений Т, упорядочивающее n случайных элементов, имеет не меньше /г! листьев. Более того, в точности п\ листьев появляются с вероятностью 1/n! каждый, а остальные -- с вероятностью 0. Не изменяя средней глубины дерева Т можно удалить из него все узлы, которые являются предками только листьев вероятности 0. Тогда останется дерево Т' с n! листь-ями, каждый из которых достигается с вероятностью 1/п!. Так как D(Т')n! log n!, то средняя глубина дерева Т' (а значит, и Т) не меньше (1/n!) n! log n! = log n!.

Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп log n сравнений для некоторой постоянной с>0.

Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сn lоg n для некоторой постоянной с (как и у вся-кой сортировки с помощью сравнений), но составляет лишь часть времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений это не существенно.

Procedure БЫСТРСОРТ(S):

if S содержит не больше одного элемента then return S

else

begin выбрать произвольный элемент a из S;

пустьS1, S2 и S3 -- последовательности элементов из S,

соответственно меньших, равных и больших а;

return (БЫСТРСОРТ(S1), затем S2, затем БЫСТРСОРТ (S3))

end

Рисунок 3.7. Программа Быстрсорт.

Алгоритм 3.5. Быстрсорт

Вход. Последовательность S из n элементов aь a2, ... , aп.

Выход. Элементы последовательности S, расположенные по порядку.

Метод. Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит в вызове БЫСТРСОРТ(S).

Теорема 3.8. Алгоритм 3.5. упорядочивает последовательность из п элементов за среднее время О (п log п).

Доказательство. Корректность алгоритма 3.5 доказы-вается прямой индукцией по длине последовательности S. Чтобы проще было анализировать время работы, допустим, что все элементы в S различны. Это допущение максимизирует размеры последова-тельностей S1 и S3, которые строятся в строке 3, и тем самым мак-симизирует среднее время, затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (n) -- среднее время, затрачиваемое алгоритмом БЫСТРСОРТ на упорядочение последовательности из n элементов. Ясно, что Т(0)=Т(1)=b для некоторой постоянной b.

Допустим, что элемент а, выбираемый в строке 2, является 1-м наименьшим элементом среди n элементов последовательности S. Тогда на два рекурсивных вызова БЫСТРСОРТ в строке 4 тратится среднее время Т(i - 1) и Т (n - i) соответственно. Так как i равно-вероятно принимает любое значение между 1 и n, а итоговое по-строение последовательности БЫСТРООРТ(S) очевидно занимает время cn для некоторой постоянной с, то

T(n)cn+[T(i-1)+T(n-1)] для n2 (3.3)

Алгебраические преобразования в (3.3) приводят к неравенству

T(n)cn+T(i) (3.4)

Покажем, что при n2 справедливо неравенство Т (n)<kn 1n n, где k=2с+2b и b=Т(0)=T(1). Для базиса (n=2) неравенство Т(2)2с+2b непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в виде

T(n)cn + + ki ln i (3.5)

Так как функция i ln i вогнута, легко показать, что

i ln i x ln x dx (3.6)

Подставляя (3.6) в (3.5), получаем

T(n)cn + + kn ln n -

Поскольку n2 и k=2с+2b, то сn+4 b/nkn/2. Таким образом, неравенство Т (n)kn 1n n следует из (3.7).

Рассмотрим две детали, важные для практической реализации алгоритма. Первая -- способ "произвольного" выбора элемента а в строке 2 процедуры БЫСТРСОРТ. При реализации этого опера-тора может возникнуть искушение встать на простой путь, а именно всегда выбирать, скажем, первый элемент последовательности S. Подобный выбор мог бы оказаться причиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из (3.3). После-довательность, к которой применяется подпрограмма сортировки, часто бывает уже "как-то" рассортирована, так что первый элемент мал с вероятностью выше средней. Читатель может проверить, что в крайнем случае, когда БЫСТРСОРТ начинает работу на уже упо-рядоченной последовательности без повторений, а в качестве эле-мента а всегда выбирается первый элемент из S, в последователь-ности S всегда будет на один элемент меньше, чем в той, из которой она строится. В этом случае БЫСТРСОРТ требует квадратичного числа шагов.

Лучшей техникой для выбора разбивающего элемента в строке 2 было бы использование генератора случайных чисел для порожде-ния целого числа i, 1<i<|S| 1), и выбора затем i-го элемента из S в качестве а. Более простой подход -- произвести выборку элемен-тов из S, а затем взять ее медиану в качестве разбивающего элемен-та. Например, в качестве разбивающего элемента можно было бы взять медиану выборки, состоящей из первого, среднего и послед-него элементов последовательности S.

Вторая деталь -- как эффективно разбить S на три последова-тельности S1, S2 и S3? Можно (и желательно) иметь в массиве А все n исходных элементов. Так как процедура БЫСТРСОРТ вызы-вает себя рекурсивно, ее аргумент S всегда будет находиться в по-следовательных компонентах массива, скажем A[f], A[f+1], ..., A[l] для некоторых f и l, 1<f<n. Выбрав "произвольный" элемент а, можно устроить разбиение последовательности S на этом же месте. Иными словами, можно расположить S1 в компонентах A[f], A[f+1], ... A[k], а S2S3-- в A[k+1], A[k+2], ..., A[l] при некотором k, fklЗатем можно, если нужно, расщепить S2S3, но обычно эффективнее просто рекурсивно вызвать БЫСТР-СОРТ на S1 и S2S3, если оба этих множества не пусты.

По-видимому, самый легкий способ разбить S на том же месте -- это использовать два указателя на массив, назовем их i и j. Вначале

begin

i f;

while ij do

begin

while A[i]>а и j>f do jj - 1;

while A[j]<а и il do ii + 1;

if < j then

begin

переставить А[i] и A[j];

ii + 1;

ij -1

end

еnd

еnd

Рис. 3.8. Разбиение S на S1 и S2S3 на месте их расположения.

i=f, и все время в A [f], ..., А [i-1] будут находиться элементы из S1. Аналогично вначале i=f, а в A[j+1], ..., A[l] все время будут находиться элементы из S2S3. Это разбиение производит подпрограмма на рис. 3.8.

Затем можно вызвать БЫСТРСОРТ для массива A[f], ... A[i--1], т.е. S1 и для массива A[j+1], ..., А[1], т.е. S2S3. Но если i=f то надо сначала удалить из S2S3 хотя бы один элемент, равный а. Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последова-тельностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива.

Пример 3.5. Разобьем массив А

1

2

3

4

5

6

7

8

9

6

9

3

1

2

7

1

8

3

по элементу а=3. while-оператор (строка 4) уменьшает j с 9 до 7, поскольку числа A[9]=3 и A[8]=8 оба не меньше а, но A[7]=1<а. Строка 5 не увеличивает i с его начального значения 1, поскольку A[1]=6а. Поэтому мы переставляем A[1] и A [7], полагаем i=2, j=6 и получаем массив на рис. 3.9, а. Результаты, получаемые после следующих двух срабатываний цикла в строках 3--9, пока-заны на рис. 3.9, б и в. В этот момент i>j, и выполнение while-опе-ратора, стоящего в строке 3, заканчивается.

Страницы: 1, 2, 3, 4



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.