Поиск и другие операции над таблицами
Любой способ поиска оперирует с элементами, которые будем называть именами, взятыми из множества имен
- оно называется пространством имен. Это пространство имен может быть конечным или бесконечным. Самыми распространенными пространствами имен являются множества целых чисел с их числовым порядком (нумерацией), и множества последовательностей символов над некоторым конечным алфавитом с их лексикографическим (то есть словарным) порядком. Каждый из алгоритмов поиска, обсуждаемых в этой лекции, основан на одном из трех следующих предположений о пространстве
.
Предположение 1. На
определен линейный порядок, называемый естественным порядком и обозначаемый знаком <. Такой порядок имеет следующие свойства.
- Любые два элемента сравнимы, то есть должно выполняться в точности одно из трех условий: , , .
- Порядок обладает транзитивностью, то есть если и , то для любых элементов . Мы используем обозначения , , в очевидном смысле. При анализе эффективности алгоритма поиска полагаем, что исход (, или ) зависит от сравнения.
Предположение 2. Каждое имя в
есть последовательность символов или цифр над конечным линейно упорядоченным алфавитом
. Естественным порядком на
является лексикографический порядок, индуцированный линейным порядком на
. Мы полагаем, что исход (
,
или
) сравнения двух символов (не имен) получается за время, не зависящее от
или
.
Предположение 3. Имеется функция
, которая равномерно отображает пространство имен
в множество
, то есть все целые
, приблизительно с одинаковой частотой являются образами имен из
при отображении
. Мы полагаем, что функция
не зависела от
, это с теоретической точки зрения выглядит шатко, но с практической - довольно реально.
Как уже было отмечено, поиск производится не в самом пространстве
имен, а в конечном подмножестве
множества
, называемом таблицей. На большинстве таблиц, которые мы рассматриваем, определен линейный порядок, называемый табличным порядком: ему соответствует нижний индекс имени (то есть
есть первое имя в таблице,
- второе и тому подобное).
Содержание Назад Вперед