Последовательность - сравнение
Cтраница 1
Последовательность сравнений, выполняемых алгоритмом бинарного поиска, предопределена: конкретная последовательность используется в зависимости от значения искомого ключа и значения N. В бинарном поиске используется один путь в дереве, тогда как при сортировке слиянием - все пути. Это дерево является статическим и неявным; в разделе 12.5 будут рассматриваться алгоритмы, в которых для выполнения поиска используется динамическая, явно построенная структура бинарного дерева. [1]
На первом просмотре последовательность сравнений будет такой, как показано в заголовках столбцов справа от исходного списка. Числа, используемые при сравнении, помечены звездочками; стрелка указывает обмен, выполняемый в результате сравнения. [2]
Сложность метода, определяющего последовательность сравнений, зависит от того, как много информации о структуре используется в организации записей. Линейный алгоритм предполагает отсутствие структуры в списке, который он упорядочивает. Список рассматривается как линейная последовательность элементов, и последовательность их сравнений и пересылок отражает этот факт. Сравниваемые элементы выбираются последовательно сверху или снизу списка один за другим. Нелинейные методы, наоборот, предполагают наличие структуры у списков, которые они сортируют. [3]
При анализе алгоритма 6.5 полезно описать последовательность сравнений г: xt как расширенное бинарное дерево ( см. разд. [4]
Сортировки могут быть охарактеризованы сложностью метода определения последовательности сравнений, комбинацией используемых методов, основным способом упорядочения я объемом необходимой памяти. [5]
Существует ряд определенных вариантов, которые различаются последовательностями сравнений элементов списка. Во всех элементарных методах обмена элемент сравнивается со своим ближайшим соседом, а гюзмож-ными перемещениями являются перемещение элемента с большим ключом на одну позицию вниз и перемещение элемента с меньшим ключом на одну позицию вверх. Парный обмен, стандартный обмен и просеивание являются тремя простыми формами сортировки обменом. [6]
Процедура упорядочения, как правило, сводится к последовательности сравнений значений признаков некоторых пар объектов и перераспределению объектов по позициям в зависимости от результатов сравнения. [7]
 |
Быстрая сортировка, конец этапа. PIVOT представляет временную ячейку, в которой находится 6. [8] |
Положение указателей BEG и END показано в конце последовательности сравнений. [9]
Методы цифрового поиска заменяют сравнение между двумя именами последовательностью сравнений между символами в их представлениях. Так как на каждый символ представления требуется только по одному такому сравнению, то время поиска пропорционально ( средней) длине имен. [10]
Образно говоря, если ui Rp ctj, то последовательность сравнений, представленная путем р, выясняет, что а о /, поскольку никакой элемент не сравнивается сам с собой. [11]
Напомним, что в теореме 4.3 каноническое разложение р-адического числа получается из последовательности сравнений. Лемма Гензеля подтверждает эту связь. Следующая теорема делает связь между р-адически-ми числами и сравнениями еще более очевидной. [12]
Форма сравнений в сортирующих сетях может быть использована в универсальной многопроцессорной системе. Сердцем такой сортировки является построение последовательностей непересекающихся сравнений, таким образом, некоторое число процессоров может работать, как независимые устройства сравнения. В этом методе дополнительные затраты образуются из-за построения нужных последовательностей сравнения. [13]
 |
Итог просмотров в лучшем случае - процессор доступен в любой момент. [14] |
Однако, возможны случаи, как на рис. 20.16, когда их можно проводить параллельно. Если N известно, то можно заранее составить полный план работы, так как последовательность сравнений не зависит от исходной упорядоченности в списке. На рис. 20.17 изображен заключительный этап. Обратите внимание, что с самого начала последнего этапа ни один элемент не удален более чем на одну позицию от той позиции, которая соответствует его значению. [15]
Страницы: 1 2