Информатика. Текстовый редактор (стр. 4 из 5)
Теперь мы утверждаем, что дерево решений Т, упорядочивающее n случайных элементов, имеет не меньше /г! листьев. Более того, в точности п\ листьев появляются с вероятностью 1/n! каждый, а остальные — с вероятностью 0. Не изменяя средней глубины дерева Т можно удалить из него все узлы, которые являются предками только листьев вероятности 0. Тогда останется дерево Т' с n! листьями, каждый из которых достигается с вероятностью 1/п!. Так как D(Т')
n! logn!, то средняя глубина дерева Т' (а значит, и Т) не меньше (1/n!) n! logn! = logn!.Следствие. Любая сортировка с помощью сравнений выполняет в среднем не менее сп logn сравнений для некоторой постоянной с>0.
Заслуживает упоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее время его работы, хотя и ограничено снизу функцией сnlоgn для некоторой постоянной с (как и у всякой сортировки с помощью сравнений), но составляет лишь часть времени работы других известных алгоритмов при их реализации на большинстве существующих машин. В худшем случае Быстрсорт имеет квадратичное время работы, но для многих приложений это не существенно.
ProcedureБЫСТРСОРТ(S):
1. ifS содержит не больше одного элемента thenreturnS
else
beginвыбрать произвольный элемент a из S;
2. пустьS1, S2 и S3 — последовательности элементов из S,
соответственно меньших, равных и больших а;
3. 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)] дляn 2 (3.3)Алгебраические преобразования в (3.3) приводят к неравенству
T(n)
cn+ 
T(i) (3.4)Покажем, что при n
2 справедливо неравенство Т (n)<kn 1nn, где k=2с+2b и b=Т(0)=T(1). Для базиса (n=2) неравенство Т(2) 
2с+2b непосредственно вытекает из (3.4). Для проведения шага индукции запишем (3.4) в видеT(n)
cn + 
+ 
kilni (3.5)Так как функция ilni вогнута, легко показать, что
i ln i 
x ln x dx 
(3.6)Подставляя (3.6) в (3.5), получаем
T(n)
cn + + knlnn - 
Поскольку n
2 и k=2с+2b, то сn+4 b/n kn/2. Таким образом, неравенство Т (n) kn1nn следует из (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], а S2
S3— в A[k+1], A[k+2], ..., A[l] при некотором k, f k lЗатем можно, если нужно, расщепить S2 S3, но обычно эффективнее просто рекурсивно вызвать БЫСТРСОРТ на S1 и S2 S3, если оба этих множества не пусты.По-видимому, самый легкий способ разбить S на том же месте — это использовать два указателя на массив, назовем их i и j. Вначале
1. begin
2. i
f;3. while i
jdobegin
4. while A[i]>аи j>f do j
j - 1;5. while A[j]<аи i
l do i i + 1;6. if < j then
begin
7. переставить А[i] и A[j];
8. i
i +1;9. i
j -1end
еnd
еnd
Рис. 3.8. Разбиение S на S1 и S2
S3 на месте их расположения.i=f, и все время в A [f], ..., А [i-1] будут находиться элементы из S1. Аналогично вначале i=f, а в A[j+1], ..., A[l] все время будут находиться элементы из S2
S3. Это разбиение производит подпрограмма на рис. 3.8.Затем можно вызвать БЫСТРСОРТ для массива A[f], ... A[i—1], т.е. S1 и для массива A[j+1], ..., А[1], т.е. S2
S3. Но если i=fто надо сначала удалить из S2 S3хотя бы один элемент, равный а. Удобно удалять тот элемент, по которому производилось разбиение. Следует также заметить, что если это представление в виде массива применяется для последовательностей, то можно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую и последнюю ячейку используемого куска массива.Пример 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, заканчивается.