Метод параллельно-последовательной свертки. Алгоритм сортировки слиянием. Оценка его вычислительной сложности

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

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

Процесс формирования подмножеств данным методом осуществляется следующим образом: до начала свёртки в качестве кандидатов на объединение рассматриваются все элементы множества Х. На первом шаге оценивают соответствие элементов некоторому критерию и выбирают элементы, в наибольшей степени удовлетворяющие ему. В общем случае могут объединятся 2,3 и т.д. элементов. Сформированные подмножества рассматриваются, как элементы нового множества, по отношению к которому процедура может быть повторена. Включение в состав формирующегося множества элементов или частей других подмножеств, как правило, не возможна в соответствии со смыслом задачи. При объединении элементов происходит отсечение других вариантов состава подмножеств, следовательно, точность получаемого решения определяется тем, является ли критерий выбора отсекающей оценкой или оценкой перспективности. В первом варианте решение может быть получено точное, во втором – приближённое.

Возможно два варианта окончания свертки:

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

2. Требуется выделить подмножество удовлетворяющее некоторым ограничениям. Процесс свёртки заканчивается при удовлетворении всех условий.

Алгоритм сортировки слиянием:

Алгоритм сортировки слиянием является примером точного алгоритма, реализующего метод уравновешенной двоичной свёртки.

Идея алгоритма: попарно сравнивая числа исходного множества (впоследствии это числа, принадлежащие двум разным подмножествам), заносят их в подмножества, состоящие из двух, четырёх и т.д. чисел, записывая, например, сначала меньшее из чисел пары. Алгоритм заканчивает работу, когда исходные числа объединены в одно (новое) множество.

Характерными особенностями реализации метода уравновешенной двоичной свёртки в данном случае являются:

- Критерий слияния подмножеств – их принадлежность одному уровню дерева свёртки; он не связан с целевой функцией, но позволяет построить достаточно эффективную схему сортировки

- Сортировка обеспечивается упорядочиванием элементов каждого подмножества при его получении слиянием двух подмножеств предыдущего уровня

- Окончание процесса свёртки означает реализацию на множестве чисел Х отношения порядка (по возрастанию их значений)

 

Оценка количества операций сравнения N_c, необходимых для упорядочивания n элементов множества Х алгоритма слияния. Если n – степень двойки, то количество подмножеств (вершин) на уровне и число элементов в них – 2^j-1, где . Число сравнений элементов двух подмножеств уровня будет . Суммарное количество сравнений на уровне j равно:

. Суммируя по j, получим: .

Очевидно, что , в то время как алгоритм сортировки «выбором» (посредством поиска максимального или минимального элемента) требует операций сравнения чисел.