Глава 5. Битовая сложность

Тривиальный способ умножения булевых (n х п)-матриц требует в(п³) битовых операций. Если используется именно этот способ, то оценка числа операций для формулы (23.2) есть в(п⁴). Приме­нение бинарного алгоритма (пример 4.2) для возведения в степень булевой матрицы С позволяет перейти к оценке

6(n³logn). (23.3)

Если нежелательно связывать основанный на формуле (23.2) алго­ритм построения транзитивно-рефлексивного замыкания с конкрет­ным способом умножения матриц, то верхнюю оценку числа битовых операций можно записать как

n+B(n)(A(n)+A*(n)-2), (23.4)

где В{п) — сложность используемого алгоритма умножения булевых (п х п)-матриц; слагаемое п отражает расход на сложение с матри­цей I.

Рассмотренный пример высвечивает связь задачи построения транзитивно-рефлексивного замыкания ориентированного графа с за­дачей умножения булевых матриц. Эта связь оказывается очень тес­ной, о чем мы еще будем говорить в § 28.

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

Пример 23.2. Исследуем сложность алгоритма С. Уоршелла, пред­назначенного для построения матрицы С*. В процессе применения этого алгоритма матрица С* строится за n = |V| шагов, после fc-го шага получается матрица D^(fc) = (d?⁵), и d?) = ^ если и только если i-я вершина соединена таким путем с j-й, номера всех промежуточ­ных вершин которого не выходят за пределы множества {1,2,..., А:}. Вначале полагаем D⁽⁰⁾ =/ V С. Затем для каждого к = 1, 2,..., п нахо­дим D«:

d^m = d*^_1) V (d (,^fc~^u Л d*^_1) ). (23.5)

у у ifc kj ^K

После этого C* = D⁽ⁿ\

Формула (23.5) отражает то, что путь из i-й вершины в j-ю, все промежуточные вершины которого принадлежат {1,2,..., А:}, суще­ствует, если и только если реализуется хотя бы одна из следующих возможностей:

• имеется путь из i-й вершины в j-ю, все промежуточные вершины которого принадлежат {1, 2, ...,к - 1};

§ 23. Булева арифметика

153

• имеются пути из i-й вершины в k-ю и из k-й в j-ю, все промежу­точные вершины которых принадлежат {1, 2,..., k - 1}.

На вычисление D⁽⁰⁾ уходит n битовых операций, вычисление каж­дой из матриц D^(k), 1^k^n, требует 2n² операций. Итого, требуется 2n³ + n операций.

Алгоритм Уоршелла вычисляет матрицу C*, т. е. строит транзи-тивно-рефлексивное замыкание ориентированного графа G с n верши­нами, заданного матрицей смежности, затрачивая 2n³ + n битовых операций.

Алгоритм Уоршелла можно легко реализовать так, что храниться в памяти будут только D^{( k}-¹⁾ и D^{( k)}. Но на самом деле алгоритм Уор­шелла позволяет производить все вычисления, расходуя всего n² би­тов под хранение матричных элементов. Если мы вычислим D = I V C, а затем n раз обновим матрицу D (каждый раз всю целиком, не оставляя незатронутых элементов), используя на k-м этапе обновле­ния матрицы D присваивания

d_ij:=d_ijV(d_ikAd_kj),

k = 1,2, ...n, то получим искомую матрицу связности. В самом деле, индукцией по k можно доказать, что после k-го этапа обновления по­лучаем матрицу, равную D^{( k)}, при этом индуктивный переход от k - 1 к k основывается на том, что имеют место очевидные соотношения

dik dik , dkj dkj

k = 1, 2, ...,n, т.е. при обновлении элемента d_ij на k-м этапе не име­ет никакого значения, был ли уже обновлен какой-то из элементов d_ik, d_kj или нет.

Если строить матрицу C* на месте исходной матрицы C, то алго­ритм можно изобразить так:

for l = 1 to n do c_ll:=1 od; for k=1 to n do for i = 1 to n do for j = 1 to n do

c_ij:=c_ijV(c_ikAc_kj) od od od

Подводя итог рассмотрению алгоритма Уоршелла, заметим, что, как и алгоритм Евклида в расширенной версии, он дает довольно

154