Число - сравнение
Cтраница 2
Число сравнений в этом методе зависит от числа просмотров, которое в свою очередь зависит от перемещения ключа, наиболее удаленного от своей конечной позиции. [16]
Число сравнений для этого - метода зависит от числа просмотров, необходимых для упорядочения данных. Ка каждом просмотре будет Л - 1 сравнение, где К есть число неупорядоченных элементов списка к началу каждого просмотра. [17]
 |
Пример множества S при d 2. [18] |
Это число сравнений ограничено снизу величиной log2Q ( S), где Q ( S) - число различных подмножеств S, получаемых как ответы на запросы. Обращаясь к рис. 2.26, рассмотрим следующее множество [ Bentley, Maurer ( 1980) ]: S - множество всех точек, имеющих одну и только одну ненулевую целочисленную координату в интервале [ - а, а ]; ясно, что N lad. Затем выберем независимо по каждой оси координат два любых целых числа в интервалах соответственно 1-а, - 1 ] и [ 1, а ]; они и определят регион запроса, для которого подмножество связанных с ним точек непусто и отлично от всех других подмножеств. [19]
Проведено также-большое число сравнений между популяциями одного вида или близкородственными видами, в которых отмечено хорошее соответствие г / / ( - схеме. [20]
 |
Построение дерева. [21] |
Минимум числа сравнений достигается при минимальном объеме дерева. У двоичного дерева объем минимален, когда минимальна его высота. На рис. 4.8 показано полностью построенное дерево ( каждая вершина либо свободна, либо хорошая); у него минимальное количество уровней и минимальный объем. [22]
 |
Оптимальная расстановка. [23] |
Максимум числа сравнений достигается, когда каждый элемент должен пройти путь от медианы до концевой позиции. Этот путь удлиняется при каждом последовательном просмотре. При первом просмотре выполняется одно сравнение ( с медианой), при втором - два, на последнем - NJ2 сравнений. [24]
Максимум числа сравнений достигается, когда на каждом этапе основа выбирается наихудшим образом. В этом случае на каждом этапе строится только одна правильная часть. [25]
 |
Минимальная по памяти турнирная сортировка, просмотр 4. [26] |
Максимум числа сравнений первого просмотра достигается при расстановках, где каждый узел меньше своего потомка и, чтобы разместить вытесненные узлы, приходится спускаться к концевым узлам. [27]
Попытка минимизировать число сравнений во вспомогательном списке, уменьшив число частей, потребовала бы дополнительных сравнений в соответственно увеличенных частях. [28]
Ксожа-лению, число сравнений имен в худшем случае Cn k пропорционально п2, и поэтому, хотя этот алгоритм и хорош в среднем, он может быть чрезвычайно неэффективным. [29]
Оценим теперь число скалярных сравнений, производимых при работе алгоритма. Аналогично на последней, ( п - 1) - й итерации число скалярных сравнений не превышает К. [30]
Страницы: 1 2 3 4 5