Главная Промышленная автоматика.

также рассматривать как соответствие некоторым начальным упорядочиваниям данных, которые "привели" программу сортировки к такому "состоянию". Можно также сказать, что данное программное "состояние" соответствует нашим знаниям о первоначальном упорядочивании исходных данных, которые можно получить на данном этапе выполнения программы.

Если какой-либо узел соответствует нескольким упорядочиваниям исходных данных, то программа на этом этапе не может точно определить истинный порядок данных и поэтому необходимо выполнить следуюшее сравнение ключей, например "является ли ki < fCj?". В зависимости от возможных ответов на этот вопрос создаются два сына этого узла. Левый сын соответствует случаю, когда значения ключей удовлетворяют неравенству ft, < кг; правый сын соответствует упорядочению при выполнении неравенства ki > Агг-*" Таким образом, каждый сын "содержит" информацию, доступную родителю, плюс сведения, вытекаюшие из ответа на вопрос, "является ли ki < кТ.

Пример 8.8. Рассмотрим алгоритм сортировки вставками при « = 3. Предположим, что элементы Л[1], Л[2] и А[3] имеют значения ключей а, Ь п с соответственно. Три элемента а, бис можно упорядочить шестью различными способами, поэтому дерево решений начнем строить с узла, представляюшего все возможные упорядочивания и помеченного на рис. 8.5 цифрой (1). Алгоритм сортировки вставками сначала сравнивает значения ключей элементов А[1] и А[2], т.е. сравнивает значения а и Ь. Если Ь меньше а, то возможны только три правильных упорядочивания Ьас, Ьса и сЬа, где Ь предшествует а. Эти три упорядочивания соответствуют узлу (2) на рис. 8.5. Другие три упорядочивания (если а меньше Ь, т.е. а предшествует Ь) соответствуют узлу (3), правому сыну узла (1).

Теперь посмотрим, что делать дальше, если исходные данные таковы, что в процессе сортировки мы достигли узла (2). Алгоритм сортировки вставками поменяет местами элементы Afi] и А[2], после чего получим текушее упорядочение Ьас. Далее проводится сравнениэ элементов А[3] и А[2]. Так как теперь А[2] содержит элемент с ключом а, то сравниваются ключи а и с. Узел (4) соответствует двум упорядочиваниям из узла (2), когда значение с предшествует значению а, узел (5) соответствует случаю, когда а меньше с.

Если алгоритм достиг узла (5), то сортировка заканчивается, поскольку этому узлу соответствует одно упорядочивание элементов Ьас. Если алгоритм находится в "состоянии" узла (4), т.е. неравенство AfS] < А[2] истинно, тогда эти элементы переставляются местами: получаем текушее упорядочение Ьса. Далее сравниваются А[1] и А[2], т.е. значения ключей с и Ь. Узлы (8), (9) соответствуют двум возможным вариантам отношения между значениями с и Ь. Если состояние программы соответствует узлу (8), то опять переставляются элементы А[1] и А[2]. В каком бы из узлов ((8) или (9)) ни находилась программа сортировки, ее выполнение заканчивается, так как этим узлам (точнее, листьям дерева решений) соответствуют по одному упорядочению элементов.

Поддерево, исходяшее из узла (3), полностью симметрично рассмотренному нами поддереву, исходяшему из узла (2), поэтому его описание мы опускаем. Дерево решений, показанное на рис. 8.5, позволяет найти правильный порядок расположения записей, соответствуюший значениям ключей а, b я с, поскольку все его листья соответствуют какому-либо Одному упорядочению. П

Можно предполагать, что значения всех ключей различны, поскольку если мы можем сортировать элементы с различными ключами, то, несомненно, сможем упорядочить элементы и с совпадающими ключами.

Здесь а, Ь и с не "буквы", а буквенное обозначение значений ключей. Поэтому может быть а<ЬиЬ<а. - Прим. ред.




(11)

Рис. S.5. Дерево решений для алгоритма сортировки вставками

Размер дерева решений

Дерево на рис. 8.5 имеет шесть листьев, соответствуюших шести возможным упорядочениям исходного списка из трех элементов а, & и с. В обшем случае, если сортируется список из п элементов, тогда сушествует п! = 1-2-...(ге - 2)(ге - \) п возможных исходов, которые соответствуют различным упорядочениям исходного списка элементов Oj, лг, а„. В самом деле, на первую позицию можно поставить любой из п элементов, на вторую - любой из оставшихся п - 1 элементов, на третью - любой из п - 2 элементов и т.д., произведение количества всех этих частных исходов дает л!. Таким образом, любое дерево решений, описываюшее алгоритм сортировки списка из п элементов, должно иметь не менее га! листьев. Фактически, если удалить узлы и листья, соответствуюшие невозможным сочетаниям элементов, получим в точности л! листьев.

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



полняемых алгоритмом сортировки в самом худшем случае. Но также не надо забывать, что, кроме сравнения ключей, алгоритм выполняет и другие операции.

Рассмотрим, какова же может быть длина путей в двоичном дереве с к листьями. Двоичное дерево, в котором все пути имеют длину р или меньше, может иметь 1 корень, 2 узла на первом уровне, 4 узла на втором уровне и далее 2 узлов на уровне i. Поэтому наибольшее число листьев 2 на уровне р, если нет узлов, выше этого уровня. Отсюда следует, что двоичное дерево с к листьями должно иметь путь длиной не менее logfe. Если положить к = л!, то получим, что любой алгоритм сортировки, использующий для упорядочивания п элементов только сравнения значений ключей, в самом худшем случае должен выполняться за время, не меньшее fi(log(n!)).

Какова степень роста величины log(n!)? По формуле Стирлинга л! можно достаточно точно аппроксимировать функцией (л/е),где е - 2.7183... - основание натурального логарифма. Поскольку log((л/e)") = п logn - п loge •= п logn - 1.44л, то отсюда получаем, что log(л!) имеет порядок п logn. Можно получить более простую нижнюю границу, если заметить, что л! является произведением не менее и/2 сомножителей, каждое из которых не превышает л/2. Поэтому га! > (л/2)". Следовательно, \og(n\)> (n/2)log(n/2)= (n/2)\ogn - л/2. Из любой приведенной оценки вытекает, что сортировка посредством сравнений требует в самом худшем случае времени порядка П(л logn).

Анализ времени выполнения в среднем

Можно ожидать, что алгоритм, который в самом худшем случае выполняется за время 0(п logn), в среднем будет иметь время выполнения порядка 0(л) или, по крайней мере, меньшее, чем 0(л logn). Но это не так, что мы сейчас и покажем, оставляя детали доказательства читателю в качестве упражнения.

Надо доказать, что в произвольном двоичном дереве с к листьями средняя глубина листьев не менее logft. Предположим, что это не так, и попробуем построить контрпример двоичного дерева Тек листьями, у которого средняя глубина листьев была бы меньше logk. Поскольку дерево Т не может состоять только из одного узла (в этом случае невозможен контрпример, так как утверждение выполняется - средняя глубина равна 0), пусть к > 2. Возможны две формы двоичного дерева Т, которые показаны на рис. 8.6.



/с листьев листьев

Рис. 8.6. Возможные формы двоичного дерева Т

f.</с листьев

Дерево на рис. 8.6,а не может быть контрпримером с минимальной средней глубиной листьев, поскольку дерево с корнем в узле л имеет столько же листьев, что и дерево Т, но его средняя глубина меньше. Дерево на рис. 8.6,6 не нарушает





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 118 119 120 121 122 123

0.002