Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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


Рис. 5.1.11. Дерево решений для n==3 элементов.

В трехэлементном дереве решений, изображенном на рис. 5.1.П, 1 : 2 обозначает сравнение at с аз; ребро с меткой 12 показывает, что ai<Ca2; конечные вершины указывают окончательный отсортированный порядок ключей Ои и а. Поскольку высота этого дерева равна трем, то для сортировки трех элементов требуется не больше чем три сравнения.

Теперь мы хотели бы рассмотреть трудоемкость в худшем случае для любого алгоритма сортировки сравнениями. Л/-элементное дерево решений для каждого такого алгоритма должно иметь по крайней мере N\ конечных вершин и будет иметь некоторую высоту h. Каково минимальное значение h, такое, чтобы Л/-элементное дерево решений высоты h имело N\ конечных вершин?

Во-первых, доказываем индукцией по h, что любое дерево высоты h имеет самое большее 2 конечных вершин. Без сомнения, при h=\ это справедливо. Далее полагаем, что каждое дерево решений высоты h-1 имеет самое большее 2" конечных вершин. Пусть Т - дерево решений высоты к. Если мы уберем корневую вершину Т, останутся два поддерева и Т, каждое имеет самое большее высоту h-1. Из предположения индукции следует, что Ti и Т имеют самое большее 2~ конечных вершин каждое. Таким образом, поскольку число конечных вершин Т равно числу конечных вершин Ti и Та, то Т имеет самое большее 2**--2*-*=2 конечных вершин.



Нижнюю границу для наименьшего значения h, такого что или hlogm, можно получить следующим образом:

Следовательно,

/i>logAf!>§ log-.

С помощью аппроксимации Стирлинга для N\ получена более точная нижняя граница. А именно при достаточно больших N, N\ = =0(Ы/еГ.

ft>log NlivN logN-moge=N logN-l.MN.

Таким образом, дерево решений каждого сортирующего сравнениями алгоритма имеет высоту по крайней мере/гЛ/" logAf-1.44/V; другими словами, каждый такой алгоритм в худшем случае имеет порядок по меньшей мере 0{NlogN).

Для средней оценки трудоемкости каждого алгоритма сортировки сравнениями также существует нижняя граница O(NlogN). Опять воспользуемся моделью Л/-элементного дерева решений.

Любой результат относительно средней трудоемкости для сортирующего алгоритма зависит от вероятностного распределения входных данных алгоритма. Анализ, который мы проведем, предполагает функцию равномерного распределения, т. е. каждая перестановка из N элементов с равной вероятностью может появиться в качестве ввода для алгоритма сортировки сравнениями. На практике это предположение может не выполняться, так как на входе сортирующего алгоритма может быть «частично» отсортированное множество.

Если каждая из N\ перестановок с равной вероятностью может получиться при данном алгоритме сортировки сравнениями, то каждая из соответствующих N\ конечных вершин Л/-элементного дерева решений будет достигнута с равной вероятностью. При этом все другие конечные вершины никогда не будут достигнуты. Тогда среднее число сравнений равно средней высоте этих N\ конечных вершин.

Теорема 5.1.1. При условии равномерного распределения вероятностей каждое N-элементное дерево решений имеет среднюю высоту по меньшей мере log{N\)N logN.

Доказательство. Пусть Я (Г, k) обозначает сумму высот всех конечных вершин дерева решений Т с k конечными вершинами, и пусть Н {k)=mm{H (Т, к)} - минимум сумм высот всех деревьев решений с k конечными вершинами. Если мы сможем показать, что Я {kyk \ogk, то для средней высоты любого дерева решений с k конечными вершинами будет выполнено Н {k)]k\ogk.

Продолжим рассуждения с помощью индукции по числу конечных вершин k. Очевидно, что при k~\ результат верен. Поэтому



полагаем, что Н{Щк \ogk для всех деревьев решений с числом конечных вершин, меньшим k.

Рассмотрим все деревья решений с k конечными вершинами. Каждое такое дерево Т имеет два поддерева Ti и Т., расположенных сразу под корнем и имеющих ki и кг конечных вершин, где h, ка<.к и ki+ +ki=k. Таким образом,

Я (Т. k)=ki+H(Ji, ki)+H(T„ k,)+k,

и минимум всех Н(Т, к) равен

Н{к)= rain {k + H(ki) + H{k2)}.

По предположению индукции Я(i)>ilog/sj и Н(kzykzlogk. Таким образом,

Н{к)к+ min {kilog ki + к Jog к}.

Легко показать, что минимум достигается при кк-. Следовательно,

H{k)k+klog-j =k\ogk.

Теперь мы можем сделать вывод, что поскольку каждое -элементное дерево решений Т имеет по крайней мере N\ конечных вершин, то

и средняя высота каждого iV-элементного дерева решений равна по меньшей мере

-logAf! logiV.

Следствие из теоремы 5.1.1 вытекает из того факта, что средняя высота каждого Л/-элементного дерева решений равна по крайней мере logAf!, а logA/!»A/ logA-l,44N; таким образом, каждый алгоритм сортировки сравнениями имеет оценку средней трудоемкости по меньшей мере 0{N logN).

Упражнения 5.1

5.1.1. Отсортируйте следующий список, используя QUICKSORT и HEAPSORT: 17 23 114 28 35 72 16 84 90 65

L5.1.2. Сортировка пузырьками (полное построение). Основная идея, заложенная в методе, известном как сортировка пузырьками (bubblesort), состоит в следующем. При каждом прохождении через список первый ключ сравнивается со вторым и меньший ставится на первое место. Второй ключ сравнивается с третьим и меньший ставится на второе место. Эта процедура продолжается до тех пор, пока не будет обработан весь список. Затем совершаются второй, третий и т. д. проходы, пока мы наконец не сделаем проход, при котором не будет произведено ни одной перестановки, Т. е. эсе ключи останутся на местах. Теперь список отсортирован.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [ 75 ] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.001