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

112. Верно ли, что для битовой сложности в среднем алгоритма пробных делений справедлива оценка п((|)^Ш)?

112. Битовая сложность в среднем алгоритма наивного умножения двух неотрицательных целых чисел а и Ъ допускает оценку Г2(т²), а тем самым —и 6(т²), где т = тах{А(а), А(Ь)}.

Указание. Битовые затраты при наивном умножении а на Ъ не могут быть меньше, чем сА(а)А*(Ь). Два случая

A(a) = m, A(b)sSm и А(а)г£т, А(Ь) = т

приводят к двум вероятностным пространствам У_ЪУ₂, состоящим из со­ответствующих пар (а, Ь) с равномерными распределениями вероятностей. Определить значения вероятностей событий А (а) = к и А(Ь) = к для произ­вольного О^к^т для каждого из пространств V_l5 V₂ и найти математи­ческие ожидания случайных величин £(a,b) = A(a), rj(a,b) = А*(Ь). В силу независимости £ и rj можно воспользоваться равенством E(£(a, b)rj(a, Ь)) = = (E(C(a,b))(Erj(a,b)).

114. Привести полное доказательство равенства (23.1).

115. Основываясь на (23.2) и бинарном алгоритме возведения в степень, построение С* можно выполнить с пространственной слож­ностью Зп² + 0(1).

115. Искомая матрица С* будет вычисляться правильно и после увеличения показателя степени в правой части (23.2).

117. Воспользовавшись утверждением, содержащимся в задаче 116, заменим показатель степени в правой части (23.2) на 2^т, где т — наименьшее целое, такое что 2^т ^ п - 1. Как изменится верхняя оцен­ка (23.4) при переходе к этой новой версии алгоритма?

117. Исследовать пространственную сложность описанного в зада­че 117 алгоритма.

119. Какой наибольшей временной сложностью может обладать алгоритм умножения булевых матриц, или, другими словами, какую верхнюю границу должна допускать функция В{п), чтобы времен­ные затраты описанного в задаче 117 алгоритма допускали бы оценку 0{п^ъ)?

119. Можно ли первую строку приведенного в § 23 псевдокода ал­горитма Уоршелла переместить в конец этого псевдокода?

Указание. Рассмотрим алгоритм в сокращенном виде, удалив эту строку из псевдокода. Влияют ли значения диагональных элементов исходной мат­рицы на значения внедиагональных элементов матрицы-результата?

121. Описать версию алгоритма Уоршелла для вычисления крат­ чайших путей между вершинами графа G, считая, что вместо матри-

Задачи

157

цы смежности дана матрица, содержащая длины соответствующих ре­бер. Если какие-то вершины не соединены, то длина ребра равна ∞. Провести анализ сложности по числу операций сложения и опера­ций нахождения минимума (раздельно) и анализ пространственной сложности. (В этой задаче мы не рассматриваем битовую сложность.)