Описания комбинаторных алгоритмов

Скачать 0.87 Mb.

Название	Описания комбинаторных алгоритмов
страница	3/13
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

1 2 3 4 5 6 7 8 9 ... 13

1.1. Бинарные вставки

Этот метод упоминается Джоном Мочли в 1946г. в первой публикации по машинной сортировке.

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

Сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д.

Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т.д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений.

При этом число сравнений для каждого j равно примерно lg(j).Число пересылок элементов при этом не изменяется и остается примерно равным N/4.

Время работы алгоритма t примерно оценивается формулой:

t=a*N² + b*N + c*N*lgN,

где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.

1.2. Двухпутевые вставки

Главный недостаток метода простых вставок заключается в том, что приходится сдвигать большое количество элементов. Метод бинарных вставок позволяет ускорить процесс поиска места для вставки очередного элемента. Однако для освобождения этого места по-прежнему необходимо подвинуть примерно 1/2j ранее рассортированных записей. В начале 50-х годов был предложен один из первых приемов, позволяющий сократить число необходимых переписей в памяти, - метод двухпутевых вставок.

Число пересылок можно сократить примерно в 2 раза (до N²/8), если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N-1,где N – число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Файл из предыдущего примера будет сортироваться следующим образом.

исходный файл
503		87		512		61		908		170		897		275

выходной файл												комментарий
						503						X = 87
					^
				87		503						X = 512
							^
				87		503		512				X = 61
			^
		61		87		503		512				X = 908
									^
		61		87		503		512		908		X = 170
					^
	61	87		170		503		512		908		X = 897
									^
	61	87		170		503		512		897	908	X = 275
					^
61	87	170		275		503		512		897	908	конеч. сост.

Из таблицы видно, что присоединение новых элементов к выходному файлу происходит как справа, так и слева от центрального элемента 503 с возможным сдвигом вправо или влево.

Необходимость отвести для выходного отсортированного массива место под 2N-1 элементов объясняется тем, что изначально неизвестно, куда относительно первой записи будут добавляться элементы. Например, если первый элемент окажется минимальным, то все последующие будут расположены справа от него, а слева останется N-1 пустых записей. Аналогично для случая, когда первый элемент наибольший, заполненными будут только N левых элементов. При реализации алгоритма необходимо следить за правой и левой границей и освобождать неиспользованные области памяти.

Время работы алгоритма t примерно оценивается формулой:

t = a*N² + b*N

где a, b - неизвестные константы, зависящие от программной реализации алгоритма.

1 2 3 4 5 6 7 8 9 ... 13

Похожие:

	Об использовании проблемно-ориентированных языков программирования... В статье рассматривается один из возможных подходов к проблемам проектирования лингвистических алгоритмов и к способам организации...		Отдела боевых алгоритмов и программ В 77 Воспоминания военных программистов отдела боевых алгоритмов и программ рлс до «Дунай-3» системы про а-35. М.: Издательство «Перо»,...
	Кормен Т.,Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание Целями освоения данной дисциплины являются как получение теоретических знаний в области организации структур данных и базовых вычислительных...		Исследование алгоритмов идентификации для систем бездатчикового векторного... Разработка и исследование алгоритмов идентификации и векторного управления в асинхронном электроприводе
	Программа вступительного экзамена для направления подготовки магистров... Рам) и языке высокого уровня. Временная и емкостная сложность алгоритмов для разных представлений. Сложность в среднем и наихудшем....		Разработка формализованного описания процессов сбора, обработки и... Данная работа посвящена разработке формализованного описания Банковских процессов средствами uml
	Руководство по оформлению описания плаката на конференцию Павт (документ ms word)* Описание плаката (с текстом в объеме одной страницы формата А4) содержит информацию о планах и начальных результатах недавно начатого...		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 22
	Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 22		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 21
	Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 17		Пример описания технических требований системного блока №1 2 2 Пример... Устройство бесперебойного питания для рабочих станций. Типовая конфигурация №1 17
	Конспект урока на тему: «Робот lego mindstorms ev3 исполнитель циклических... Конспект урока на тему: «Робот lego mindstorms ev3 – исполнитель циклических алгоритмов»		Исследование аппроксимационных алгоритмов решения обратных задач технической диагностики
	Разработка и исследование алгоритмов идентификации и векторного управления...		При обучении биологии Составление алгоритмов для формирования и развития умений и мыслительных операций

Руководство, инструкция по применению