Отчет по практике: Информатика. Текстовый редактор

Forinstep -1 until 2 do

Begin

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

ПЕРЕСЫПКА(i,i - 1)

End end

Теорема 3.6. Алгоритм 3.4 упорядочивает последовательность из п элементов за время 0(nlogп).

Доказательство. Корректность алгоритма доказывает­ся индукцией по числу выполнений основного цикла, которое обозначим через m. Предположение индукции состоит в том, что по­сле m итераций список A[n-m+1], ..., А [n] содержит m наи­больших элементов, расположенных в порядке неубывания, а спи­сок A[1], ..., А[n-m] образует сортирующее дерево. Детали до­казательства оставляем в качестве упражнения. Время выполнения процедуры ПЕРЕСЫПКА(1, i) есть 0(logi)- Следовательно, ал­горитм 3.4 имеет сложность О (nlogi ).

Следствие. Алгоритм Сортдеревом имеет временную сложность O(nlogn)

3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ О(nlogn)

До сих пор мы рассматривали поведение сортирующих алгорит­мов только в худшем случае. Для многих приложений более реа­листичной мерой временной сложности является усредненное вре­мя работы. В случае сортировки с помощью деревьев решений мы видим, что никакой сортирующий алгоритм не может иметь сред­нюю временную сложность, существенно меньшую n 1оgn. Однако известны алгоритмы сортировки, которые работают в худшем слу­чае сn² времени, где с — некоторая постоянная, но среднее время работы, которых относит их к лучшим алгоритмам сортировки. При­мером такого алгоритма служит алгоритм Быстрсорт, рассматривае­мый в этом разделе.

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

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

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

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

Базис, т. е. случай /п=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+klog =klogk

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

Теперь мы утверждаем, что дерево решений Т, упорядочивающее 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;