Стр. 21 - Основы алгоритмов и структур данных

Содержание 19
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4. Многочисленные методы искусственного интеллекта.
2-й класс. Быстрый поиск. Задача быстрого поиска в общем случае
формулируется так: исследовать некоторое множество с тем, чтобы найти
элемент или элементы, удовлетворяющие заданному критерию.
4.1. Быстрый поиск
В быстром поиске существуют две стратегии:
1. Перебор элементов (очень медленно).
2. Доступ элемента по индексу.
4.1.1. Общие положения.
Задачу быстрого поиска в общем виде невозможно решить быстрее, чем
это делается путем полного перебора всех существующих вариантов или
решений.
Полный перебор множества из n элементов требует О(n) операций
(величина примерно того же порядка). Однако достаточно небольших
ограничений на структуру исследуемого множества, чтобы возникло множество
стратегий эффективного решения. Большинство известных алгоритмов
быстрого поиска имеют быстродействие О(n), либо O(log2 n), либо О(1).
4.1.2.Основные понятия и определения
Любой метод поиска оперирует с элементами, именами или ключами из
некоторого пространства имен, которое обозначим S. В каждом конкретном
случае обрабатывается не все пространство S, а некоторое его конечное
подмножество, называемое таблицей T. Обычно, в таблице определен так
называемый табличный порядок, в котором ключи присутствуют в таблице.
Часто на пространстве S определен так называемый естественный или
линейный порядок, обозначаемый знаком <. Например, если S – натуральные
числа, то 1 < 2 и 1 связан с 2 линейным порядком. ‘abc’ < ‘abd’ < ’ b’ . Порядок
определяется не на таблице Т, а на пространстве. Линейным называется
порядок, обладающий следующими свойствами:
а) любые 2 элемента S x ∈ и S y ∈ сравнимы. Либо x < y , либо y < x, либо x и
y одно и тоже.
б) порядок обладает транзитивностью:
x y x z
y z
< 
<< 