Время выполнения сортировки методом слияния Проведя анализ наиболее важного компонента сортировки — алгоритма . Допустим, исходная последовательность имеет п элементов. Для простоты ограничимся случаем, когда п является степенью . Доказательство верности результата анализа при любом п оставлено для упражнения М. Аналогично вышеприведенному анализу допустим, что последовательность . Это возможно при реализации на основе кольцевого массива и двусвязного списка . Сортировка, множества и выборка . Необходимое для прохождения каждого узла . Другими словами, время, требуемое на один узел . Выше отмечалось, что процедура деления достаточно проста и выполняется за время, пропорциональное размеру последовательности из . Кроме того, из утверждения . Это означает, что время, затрачиваемое на узел . Рассматривая более общий случай дерева, как показано на рис. Заметьте, что Г имеет ровно . Из этого замечания вытекает, что общее время, затраченное на все узлы дерева Г на глубине . Таким образом, поскольку время, затраченное на каждый уровень . Алгоритм сортировки методом слияния сортирует последовательность размером п элементов в худшем случае за . Другими словами, алгоритм сортировки слиянием асимптотически стремится к быстрому выполнению алгоритма пирамидальной сортировки. ВысотаВремя на уровень . Время выполнения дерева сортировки Т. В узлах приведены значения размера . Сортировка, множества и выборка . Реализация сортировки методом слияния Во фрагменте кода . В этой реализации исходная последовательность . То есть каждая модификация в последовательности, реализованной двусвязным списком или с помощью цикличного массива, занимает . В данном случае речь идет о классе . Следовательно, для последовательности . Сортировка методом слияния и рекуррентные соотношения Существует еще один способ обоснования утверждения . В этом разделе содержится именно такой анализ алгоритма сортировки, и по этой причине представляется математическая концепция рекуррентных отношений . Поскольку сортировка методом слияния рекурсивна, можно охарактеризовать функцию . Такая функция называется рекуррентной, поскольку содержится в обеих частях уравнения. Для получения такой замкнутой характеристики . Один способ — итеративное решение этого уравнения, исходя из сравнительно большего значения п. После очередной итерации можно записать . Повторив еще раз, получим . Применим полученное уравнения . Теперь следует решить, когда остановить этот процесс. Сделав такую подстановку, получим . Таким образом, получено альтернативное обоснование того, что . В следующем разделе покажем, как можно использовать сортировку и алгоритм . Множеством называется контейнер из определенных объектов. То есть в множестве нет повторяющихся объектов, нет и каких. Но несмотря на это, авторы включают обсуждение АТД . При выполнении запроса по слову х такая система должна вернуть адреса страниц множества . Но при выполнении запроса на поиск двух слов х и у такая поисковая система вначале должна определить пересечение множеств . Многие поисковые системы используют для выполнения такой операции алгоритм, который описывается в этой главе. Основными методами АТД . Выше отмечалось, что операции . Однако эти операции можно определить не для изменения множества А, а для возврата нового. Он обеспечивает отсутствие во множестве одинаковых объектов и содержит методы, не отличающиеся . Сортировка, множества и выборка от описанных выше. Соответствие между вышеприведенными методами АТД и методами . Методы АТД множества Методы . Соответствие между методами АТД . Последний поддерживает еще ряд других методов . Реализация простого множества Простейшим способом реализации множества является хранение его элементов в упорядоченной последовательности. Предпочтение такой реализации заложено в интерфейсе . Даже в случае отсутствия компаратора можно определить некоторые отношения упорядоченности элементов множества. В принципе способ упорядочить элементы всегда имеется. Например, можно воспользоваться адресами объектов в памяти. Поэтому рассмотрим реализацию АТД . Каждую из трех основных операций множества реализуем с помощью унифицированной версии алгоритма слияния, который в качестве исходного данного принимает две отсортированные последовательности, представляющие исходные множества, и создает последовательность, представляющую получаемое в результате множество, будь то объединение, пересечение или разность исходных множеств. Упорядочение для обоих множеств может основываться на любом правиле . Описание унифицированного алгоритма слияния приведено во фрагменте кода . Унифицированный алгоритм слияния, использующий методы . Этот алгоритм не изменяет исходные последовательности Унифицированный метод слияния интерактивно изучает и сравнивает текущие элементы аи . После этого в зависимости от результата сравнения и выполняемой операции . Например, в операции объединения меньший элемент копируется в создаваемую последовательность, при равенстве — любой из них . Такой подход гарантирует, что копируется элемент, который присутствует только в одном из множеств, чтобы избежать дублирования. Вид копирования будет определяться вспомогательными методами . Слияние как модель проектирования Унифицированный алгоритм слияния представляет собой модель проектирования шаблонных методов . Модель проектирования шаблонных методов — это модель проектирования программ, описывающая универсальный механизм выполнения вычислений, который можно настраивать переопределением некоторых шагов. В данном случае описываем метод объединения двух последовательностей в одну. Для управления процессом объединения достаточно определить поведение трех абстрактных методов. Для конкретной реализации процесса слияния требуется создать класс. После переопределения вспомогательных методов шаблонный метод . Также можно рассмотреть расширение АТД . Посколъку применяется сортированная последовательность, эти методы можно реализовать простым сканированием последовательности, являющейся множеством, за .