Комбинаторные алгоритмы для программистов



             

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


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

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

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

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

  1. Любые два элемента
    x,y \in S
    сравнимы, то есть должно выполняться в точности одно из трех условий:
    x < y
    ,
    x = y
    ,
    y < x
    .
  2. Порядок обладает транзитивностью, то есть если
    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
- второе и тому подобное).


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