Алгоритм - включение
Cтраница 1
Алгоритмы включения и исключения имеют трудоемкость 0 ( log и), где п - число висячих вершин. [1]
Алгоритм включения проверяет ячейки до тех пор, пока не найдет пустую. Для гарантии того, что пустая ячейка встречается, если она существует, каждый адрес i, O i m - 1, должен появляться в последовательности точно один раз. По существу, эту последовательность можно представить двумя способами, которые соответствуют последовательному и связанному распределению списков ( см. разд. [2]
 |
Несбалансированность, возникшая из-за включения.| Восстановление сбалансированности. [3] |
Алгоритм включения и балансировки существенно зависит от того, каким образом хранится информация о сбалансированности дерева. [4]
Алгоритм включения атрибутов применяют к данным о молекулярной структуре иначе, чем это делал Абдали в его работе по восстановлению символов. Нас интересует прежде всего классификация образов, а не их восстановление, поэтому формирование множественных признаков мы должны рассматривать скорее как средство разбиения образов на два класса. При этом алгоритм включения атрибутов применяют раздельно к каждому такому классу, а не ко всем вместе как к единой выборке данных. К тому же множественные признаки используют совсем не как альтернативное представление исходных образов меньшей размерности. Напротив, ими пополняют исходные образы, увеличивая размерность пространства образов. [5]
В алгоритме включения ближайшего города условие локальной оптимальности более тонкое, чем в алгоритме ближайшего соседа, и поэтому можно ожидать, что он порождает маршрут, для которого гарантируется, что его стоимость ближе к стоимости оптимального маршрута, чем верхняя оценка из теоремы 4.1. Это действительно так. [6]
Приведенные выше алгоритмы включения и исключения были написаны для стеков, но они применимы и в более общем случае для включения и исключения в любом линейном списке. [7]
Можно построить натуральные алгоритмы включения и исключения букв перед рассматриваемой буквой преобразуемого квазислова. Допустим, что такие алгоритмы у нас уже есть. [8]
Теперь легко описать алгоритм включения или исключения данного имени г. Мы ищем г в дереве, начиная от корня и следуя по пути к листу. При прохождении каждого узла информация о мощности обновляется, и, если поддерево с корнем в этом узле становится несбалансированным, выполняется подходящее преобразование дерева. Как только 2 найдено ( в случае исключения) или найдено его место ( в случае включения), применяются манипуляции с указателями для включения или исключения узла, описанные в разд. Заметим, что поскольку уравновешенные по весу деревья не требуют возвращения по пути вверх к корню, нет необходимости хранить путь в стеке. [9]
Заметим, что в противоположность алгоритму включения, требующему не более одного преобразования, этот алгоритм исключения может требовать [ Л / 2 J преобразований, где h - высота всего дерева ( см. упр. Однако в большинстве случаев алгоритм исключения ( и также алгоритм включения) не потребует прослеживания восходящего пути до самого корня; обычно алгоритм завершается после некоторого числа шагов, которое не зависит от высоты дерева ( см. упр. [10]
 |
Включение в СДБ-дерево. [11] |
Поскольку мы ограничимся лишь детальным разбором алгоритма включения, нам нужно вновь разобраться в четырех случаях роста поддеревьев. Они приведены на рис. 4 52: ясно видно, что мы добились симметрии. [12]
Таким образом, теперь мы знаем, что алгоритм включения ближайшего города всегда порождает маршруты, стоимость которых превышает стоимость оптимального маршрута не больше чем в два раза. [13]
Используемый нами метод выделения признаков известен под названием алгоритма включения атрибутов. Включение атрибутов характеризует взаимосвязь между ними в той или иной выборке образов. В этом случае атрибут является синонимом дескриптора. [14]
В последовательных файлах, хранящихся на магнитных лентах, алгоритм включения и удаления записей хорошо известен. Он заключается в сортировке файла изменений в том порядке, который принят в существующем файле, в чтении записей изменений и записей существующего файла с попутным включением и удалением из последнего необходимых записей. [15]
Страницы: 1 2