Время - выполнение - сортировка
Cтраница 1
Время выполнения сортировки слиянием не чувствительно к организации входных данных. Приводимые здесь диаграммы показывают, что количество проходов, выполненное в рамках восходящей сортировки слиянием на файлах с произвольной организацией, на файлах с распределением Гаусса, на почти упорядоченных файлах, на почти обратно упорядоченных фатах и на файлах с произвольной организацией, обладающих 10 различными ключами ( слева направо), зависит только от размера файла и не зависит от того, какими являются входные значения. Подобное поведение находится в резком противоречии с поведением быстрой сортировки и поведением множества других алгоритмов. [1]
Время выполнения сортировки вставками зависит от общего числа инверсий в файле и не зависит от того, каким образом эти инверсии распределены в файле. [2]
Лемма 6.6. Время выполнения сортировки выбором линейно зависит от размеров файлов с большими элементами и малыми ключами. [3]
Таким образом, основную составляющую времени выполнения сортировки представляет количество осуществленных операций сравнения. В разделе 6.5 будет показано, что это время пропорционально TV2, а также представлены способы вычисления общего времени выполнения программы сортировки и корректного сравнения сортировки выбором и других элементарных методов. [4]
В отличие от сортировки выбором, время выполнения сортировки вставками зависит главным образом от исходного порядка ключей при вводе. Например, если файл большой, а ключи записей уже упорядочены ( или почти упорядочены), то сортировка вставками выполняется быстро, а сортировка выбором протекает медленно. [5]
 |
Эмпирические исследования элементарных алгоритмов сортировки. [6] |
Как было только что отмечено, время выполнения сортировки вставками прямо пропорционально количеству инверсий в сортируемом файле. [7]
Если 7V не велико, то такое время выполнения сортировки может оказаться вполне приемлемым. [8]
Для более коротких ключей и более длинных байтов время выполнения сортировки сопоставимо с N: например, если по отношению к 64-разрядным ключам используется 16-разрядное основание системы счисления, то w принимает значение 4, что можно считать константой малого значения. [9]
Имея 1 миллион 32-разрядных ключей, найти такой размер байта, для которого время выполнения сортировки будет минимальным в условиях, когда используется метод, предусматривающий поразрядную сортировку LSD по двум первым байтам и последующую подчистку нарушений искомого порядка через сортировку простыми вставками. [10]
 |
Эмпирическое исследование алгоритмов быстрой сортировки. [11] |
Совершенствование метода отсечения меньших подфайлов и метода медианы из трех элементов ( программа 7.4) сокращают время выполнения сортировки примерно на 10 процентов каждое. [12]
Очередность, в которой производится обработка подфайлов, не препятствует корректному выполнению алгоритма быстрой сортировки и не приводит к увеличению времени выполнения сортировки, однако может повлиять на размеры стека магазинного типа, положенного в основу рекурсивной структуры. В рассматриваемом случае первым обработке подвергается меньший из подфайлов, образованных в результате каждого разделения. [13]
Показать, что если внести изменения в программу 7.4, предусматривающие исключение первой операции обмена и пропуск ключей, равных разделяющему элементу, то время выполнения сортировки файла, организованного в обратном порядке, находится в квадратичной зависимости от длины файла. [14]
Тем не менее, для двоичной быстрой сортировки вероятность того, что разделяющая точка находится в окрестности центра, выше, чем для стандартного метода быстрой сортировки, так что старший член выражения, определяющего время выполнения сортировки, тот же, что и для случая, когда разделение идеально. [15]
Страницы: 1 2