Поиск и другие операции над таблицами

Любой способ поиска оперирует с элементами, которые будем называть именами, взятыми из множества имен

$S$

- оно называется пространством имен. Это пространство имен может быть конечным или бесконечным. Самыми распространенными пространствами имен являются множества целых чисел с их числовым порядком (нумерацией), и множества последовательностей символов над некоторым конечным алфавитом с их лексикографическим (то есть словарным) порядком. Каждый из алгоритмов поиска, обсуждаемых в этой лекции, основан на одном из трех следующих предположений о пространстве

$S$

Предположение 1. На

$S$

определен линейный порядок, называемый естественным порядком и обозначаемый знаком <. Такой порядок имеет следующие свойства.

Любые два элемента
$x,y \in S$
сравнимы, то есть должно выполняться в точности одно из трех условий:
$x < y$
,
$x = y$
,
$y < x$
.
Порядок обладает транзитивностью, то есть если
$x < y$
и
$y < z$
, то
$x < z$
для любых элементов
$x,y,z \in S$
. Мы используем обозначения
$>$
,
$\leqslant$
,
$\geqslant$
в очевидном смысле. При анализе эффективности алгоритма поиска полагаем, что исход (
$<$
,
$=$
или
$>$
) зависит от сравнения.

Предположение 2. Каждое имя в

$S$

есть последовательность символов или цифр над конечным линейно упорядоченным алфавитом

$A = \{ a_1,a_2,\ldots,a_c \}$

. Естественным порядком на

$S$

является лексикографический порядок, индуцированный линейным порядком на

$A$

. Мы полагаем, что исход (

$<$

$=$

или

$>$

) сравнения двух символов (не имен) получается за время, не зависящее от

$\left| S \right|$

или

$n$

Предположение 3. Имеется функция

${h\colon S \to \{ 0,1,\ldots,m - 1}\}$

, которая равномерно отображает пространство имен

$S$

в множество

$\{ 0,1,\ldots,m - 1\}$

, то есть все целые

$i,0 \leqslant i \leqslant m - 1$

, приблизительно с одинаковой частотой являются образами имен из

$S$

при отображении

$h$

. Мы полагаем, что функция

$h$

не зависела от

$\left| S \right|$

, это с теоретической точки зрения выглядит шатко, но с практической - довольно реально.

Как уже было отмечено, поиск производится не в самом пространстве

$S$

имен, а в конечном подмножестве

$T = \{ x_1,x_2,\ldots,x_n \}$

множества

$S$

, называемом таблицей. На большинстве таблиц, которые мы рассматриваем, определен линейный порядок, называемый табличным порядком: ему соответствует нижний индекс имени (то есть

$x_1$

есть первое имя в таблице,

$x_2$

- второе и тому подобное).

Содержание Назад Вперед