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



             

Различные способы представлений


Последовательное распределение. С вычислительной точки зрения простейшим представлением конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти.


Рис. 2.1.

 

Последовательное распределение последовательности

s_1,s_2,\ldots,s_n
для каждого элемента которой требуется
d
ячеек

Так,

s_1
хранится, начиная с ячейки
l_1
,
s_2
хранится, начиная с ячейки
l_2 = l_1 + d
,
s_3
хранится, начиная с ячейки
l_3 = l_1 + 2d
и так далее, где
d
- число ячеек, требуемых для хранения одного элемента последовательности.

Описанное выше представление последовательности имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов в смысле памяти. Кроме того, оно полезно и потому, что существует простое соотношение между

i
и адресом ячейки, в которой хранится
s_i
:

l_i = l_1 + (i - 1)d.

Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. Наконец, последовательное представление имеет достаточно широкий диапазон и включает в себя в качестве специального случая представление многомерных массивов.

Например, чтобы представить массив размером

n \times m

 \left( {\begin{array}{*{20}c} {a_{11} } & {a_{12} } & {\ldots } & {a_{1m} } \\ {a_{21} } & {a_{22} } & {\ldots } & {a_{2m} } \\ . &. &. &. \\ {a_{n1} } & {a_{n2} } & {\ldots } & {a_{nm} } \\ \end{array} } \right)

(2.4)

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

s_1,s_2,\ldots,s_n
, в которой каждое
s_i
в свою очередь является последовательностью из
m
элементов
i
-й строки нашей матрицы. Таким образом, число ячеек, требуемых для записи элемента
s_i
(будем обозначать это число символом
d
), равно
m\bar d
, где
\bar d
- число ячеек, требуемых для записи элемента
a_{ij}
. Поскольку последовательность
s_i
начинается в ячейке

l_i = l_1 + (i - 1)d = l_1 + (i - 1)m\bar d,

ячейка для

a_{ij}
будет иметь следующий адрес:

l_i + (j - 1)\bar d = l_1 + [(i - 1)m + (j - 1)]\bar d.

Это представление известно как построчная запись матрицы; постолбцовая запись получается, если (2.4) рассматривать как последовательность

t_1,t_2,\ldots t_m
в которой каждое
t_i
в свою очередь является последовательностью из элементов
i
-го столбца матрицы.

Последовательное распределение, наряду с преимуществами, имеет значительные недостатки. Например, такое представление становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между

s_i
и
s_{i + 1}
нового элемента требует сдвига
s_{i + 1},s_{i + 2},\ldots,s_n
вправо на одну позицию; аналогично, исключение
s_i
требует сдвига тех же элементов на одну позицию влево. С точки зрения времени обработки, такое передвижение элементов может оказаться дорогостоящим, и в случае динамических последовательностей лучше использовать технику связного распределения, рассматриваемую в следующей лекции.

Характеристические векторы. Важной разновидностью последовательного распределения является случай, когда такому представлению подвергается последовательность некоторой основной последовательности

s_1,s_2,s_3 \ldots
В этом случае можно представить последовательность более удобно, используя характеристический вектор - последовательность из нулей и единиц, где
i
-й разряд равен единице, если
s_i
принадлежит рассматриваемой последовательности, и нулю в противном случае.

Например, характеристический вектор начального сегмента последовательности (2.3)

s_i:\quad 1 \;2 \;3 \;4 \; 5\; 6\; 7\; 8\; 9\; 10

характеристический вектор для простых чисел:

\quad 0 \;1 \; 1\; 0\; 1\; 0\; 1\; 0\; 0\;0

Здесь основной последовательностью является последовательность целых положительных чисел. В ЭВМ с 32-разрядными словами для запоминания простых чисел, меньших

10^6
, потребуется
10^6.32 = 31250
слов. Замечая далее, что для
i > 1
число
2i
не простое, можно сэкономить половину этого поля, выписывая разряды только для чисел видов
2i + 1,i \geqslant 1
, и запоминая, что простое число 2 отсутствует. Таким образом, простые числа, меньшие чем
10^6
, можно записать только 15625 словами. Поскольку число простых чисел, меньших
10^6
, равно 78498, последовательное представление, описанное ранее, потребовало бы поля в пять раз меньшего размера.

Характеристические векторы полезны в ряде случаев. Их полезность вытекает из их компактности, существования простого фиксированного соотношения между

i
и адресом
i
-го разряда и возможности при таком представлении очень легко исключать элементы.

Главное неудобство характеристических векторов состоит в том, что они не экономичны. Исключение составляют "плотные" последовательности последовательностей

s_1,s_2,s_3 \ldots
. Кроме того, их трудно использовать, если не существует простого соотношения между
i
и
s_i
.Если такое соотношение сложное, то использование характеристических векторов может быть очень не экономичным в смысле времени обработки. Если последовательности недостаточно плотные, то значительным может оказаться объем памяти. В случае простых чисел между
i
и
s_i
имеется простое соотношение:
s_i = i
(или
s_i = 2i + 1
, если использовать только нечетные числа). Теорема о простых числах утверждает, что число простых чисел, меньших
n
, приблизительно равно
n/ \ln n
; таким образом, простые числа относительно плотно распределены в множестве целых чисел.




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