Число - сравнение
Cтраница 1
Число сравнений минимально, JV - 1, когда исходный список полностью упорядочен. Число сравнений максимально, когда список имеет обратный порядок. В этом случае каждое Из N - 1 первичных сравнений порождает вторичную последовательность, что увеличивает общее расстояние от точки первичного сравнения до вершины списка. Чтобы определить ожидаемое число сравнений, учтем, что средняя длина поиска любой позиции списка равна половине длины списка. Процесс просеивания аналогичен поиску в упорядоченном списке чисел нужной позиции для нового числа. [1]
Число сравнений при любом просмотре зависит от количества элементов в списке. Пусть длина области вывода, вмещающей все ожидаемые элементы, равна N. Так как элементы поступают по одному, то область вывода не заполнена, пока сортировка не закончена. Сравниваться элементы будут при N - 1 обращении к сортировке, поскольку при первом обращении элемент только помещается в список. В худшем случае каждый новый элемент помещается вниз списка, и число сравнении на каждом просмотре равно Л / / 2 - средней длине списка для всех просмотров. Таким образом, худшим случаем для сравнений является тот, при котором элементы списка упорядочиваются в той же последовательности, в какой они поступают. Здесь мы впервые наблюдаем чувствительность к упорядоченности, когда чем лучше упорядочены данные, тем больше выполняется сравнений. [2]
Число сравнений равно минимум ( п - 1), максимум ( п - 1) / 2; первое соответствует случаю наилучшего варианта числа обменов, второе - случаю наихудшего варианта. Среднее число сравнений отклоняется от промежуточного в большую сторону. [3]
 |
Минимальная по памяти турнирная сортировка, просмотр 3. [4] |
Число сравнений при первом просмотре зависит от исходного порядка данных. Минимум этого числа достигается, когда все тройки упорядочены должным образом, и равен удвоенному числу узлов в дереве без корневого узла. [5]
Число сравнений зависит не от длины текущего списка, а от ожидаемой длины всего списка. [6]
Число сравнений при динамическом дереве равно сумме log2 К по всем просмотрам. [7]
 |
Состояние списка после каждого из пяти просмотров ( z - фиктивная. [8] |
Число сравнений никак не зависит от упорядочения начальных данных. Таким образом, для этого метода наилучшее, наихудшее и ожидаемое ( среднее) число сравнений одно и то же. [9]
 |
Распределение 961 - 1000 и сбор убывающей строки на Т. [10] |
Число сравнений при распределяющем просмотре зависит от метода, выбранного для нахождения соответствующего интервала. [11]
Число сравнений зависит от точности алгоритма. Для распределений малых степеней обычно будет использоваться простой ( N-1) - спо-соб. Для распределений очень большой степени может быть эффективным log2 N-способ с древовидными структурами. [12]
Число сравнений фактически не зависит от начального порядка элементов. [13]
Число сравнений ключей ( С), очевидно, не зависит от начального порядка ключей. [14]
Число сравнений ключей С даже меньше М, поскольку при копировании остатков никаких сравнений не производится. Однако поскольку сортировки слиянием обычно употребляются в ситуациях, где приходится пользоваться внешними запоминающими устройствами, то затраты на операции пересылки на несколько порядков превышают затраты на сравнения. Поэтому детальный анализ числа сравнений особого практического интереса не представляет. [15]
Страницы: 1 2 3 4 5