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

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

 







Дата добавления: 2015-04-19; просмотров: 592. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

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

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

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

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия