Будем называть времем работы алгоритма сортировки массива(все рассуждения могут быть перенесены на другие структуры с небольшими изменениями) кол-во сравнений


Скачать 25.95 Kb.
НазваниеБудем называть времем работы алгоритма сортировки массива(все рассуждения могут быть перенесены на другие структуры с небольшими изменениями) кол-во сравнений
Дата07.11.2012
Размер25.95 Kb.
ТипДокументы
Будем называть времем работы алгоритма сортировки массива(все рассуждения могут быть перенесены на другие структуры с небольшими изменениями) - кол-во сравнений нужных для упорядочевания его (будем считать , что алгоритм использует только сравнения при работе с массивом). Массив упорядочен , если мы знаем как соотносятся любые 2 элеметна.Процесс работы алгоритма можно представить в виде бинарного дерева. Сравнение элемента A c элементом В будем записывать так : А:В и это назовем узлом . Разветвление влево показывает А < B , вправо показывает A > B.Каждая ветка приводит к какой то перестановке исходного массива(в которой мы знаем отношение между любыми 2мя элементами) - к листу. Очевидно , что кол-во

листов равняется n! , где n - длина массива. Будем называть алгоритм - наилучшим , если он в наихудшем случае работает лучше чем все остальные.S(n) - наихудшее время наилудшего алгоритма.C(A,М)- кол-во сравнений алгаритма А на массиве M.Тогда

S(n) = min по А ( max по М ( C ( A , M))) Если сказать по другому S(n) - это самая длинная ветка в дереве разбора наилучшего алгоритма.Так же можно провести аналогию с графами - сравнением точек A и B будем называть ребро графа направелнное из точки А в В если А больше В ,и из точки В в А если В больше А.То для графа S(n) - это наибольшее число рёбер , которое нужно перебрать(в наилучшем алгоритме) для того чтобы дойти до линейного графа ( это граф по которому мы можем определить как соотносятся любые 2 элемента )

В дальнейшем нам будут нужны некоторые определения :

Определение1 :

Буквой G будем называть граф сравнений алгоритма.

Определение2 :

Введём функцию, которая по графу сравнений G , будет возвращать число способов сопоставить элементы массива из n числе , таким образом , чтобы это не противоречило графу G и назовем её T.Очевидно что результатом каждого алгоритма сортировки должен быть линейный граф , а у линейного графа T(G)=1

Определение3:

Так же введём функцию E , от графу сравнений G и колличества сравнений k

E(G,k)=n!/(2^k * T(G))

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

j=S(n) , имеем n! <= 2^S(n)

т.к S(n) - целое число то можно записать эту формулу иначе , получив нижнюю оценку :

S(n) >= ceiling ( log2 (n!) )

S(n) считается полным перебором (всего) . Для n <= 11 есть алгоритмы , которые реализуют идеальное время ceiling ( log2 (n!)) , то эти случаи не интересны.То задача подсчёта S(n) cводиться к построению(нахождению) контрпримера . То есть нам надо перебрать все алгоритмы для каждого отдельно взятого n и убедится для этого n нет алгоритма работающего за идеальное время.Здесь вылезают некие оптимизации.Но сначало докажем один факт. А именно , что на каждой итерации алгоритма сортировки эффективность графа сравнений не увеличивается.(этот факт докажется) Оптимизации:

обозначим за G*- линейный граф, k* - ceiling(log2 n! )

E*= E(G* , k^)=n!/(ceiling(log2 n!))

1) Будем выкидывать графы с эффективностью меньшей Е*

2) Графы с одинаковой эффиктивностью выкидываем

3) Если при сравнении получаются два графа разной эффективности - надо брать граф с наименьшей

Откуда берутся первые 2 пункта понятно , а откуда последний - не понятно.!!!

Можете объяснить?

Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница