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

редкий пример, когда низкие временные затраты сочетаются с малым расходом памяти.

Алгоритм Уоршелла построения замыкания ориентированного графа имеет битовую временную сложность 2n³ + n, где n = \ V \ — чис­ло вершин графа. Пространственная сложность этого алгоритма ограничена константой.

При рассмотрении |V|, |E| в качестве двух параметров размера входа сказанное сохраняет силу, так как затраты алгоритма Уоршелла не зависят от числа ребер заданного входного графа.

Задачи

98. Исследовать битовую сложность вычисления величины 1 + + 2 + ... +n последовательными сложениями. Размером входа считать битовую длину m целого числа n.

98. Для временной битовой сложности «сверхнаивного» умноже­ния (пример 19.1) при использовании параметров m_ъ m₂ верна оценка сверху O(2^тах{m1'^m2}тах{m₁,m₂}), а оценка Q(.2^max{m^^m}max{m₁,m₂}) неверна.

Указание. Неверна оценка П(2^тах{mь^m2}_тах{m₁,m₂}): она противоречила бы оценке O(2^m2m{), так как для любого N > 0 существуют m₁,m₂>N такие, что m₁ = 2^m2.

100. Определение чисел Фибоначчи, данное в § 10, позволяет вы­числить F_n, выполнив n — 1 сложение. Битовая сложность этого алго­ритма допускает оценку O{n²) при рассмотрении n в качестве разме­ра входа.

100. Обосновать использованный в доказательстве предложения 21.1 переход от оценки T*^(.m_ъm₂) = O{{m_г - m₂ + 1)(m₂ + 1)) к T^* (m_ъ m₂) = O{{m_г -m₂ + 1)m₂).

100. Можно ли усилить предложение 21.2, заменив приведенные там оценки O(logalogb), O(log²a) на e(logalogb), 6(log²a)?

100. Рассмотрим m = А(n) в качестве размера входа алгоритма вы­числения факториала (пример 20.1). Верна ли для соответствующей временной битовой сложности оценка O(2^mm)?

100. К числу, первоначально равному нулю, прибавляется шаг за шагом по единице до получения значения 2n - 1, n ^ 0. При этих сло­жениях потребуется 2n - n - 1 переносов единицы в старший разряд.

100. Пусть p — простое, a и b — произвольные целые, k — нату­ральное. Тогда (a + b)^pk=a^pk +b^pk (mod p).

100. Задачи

155

106. а) Аддитивная группа кольца Z_k является циклической, в ка­ честве образующей этой группы может выступать любой класс, со­ держащий число I, взаимно простое с к.

б) Пусть р—простое, тогда мультипликативная группа поля Z_p, т. е. группа всех ненулевых элементов по умножению, является цик­лической.

107. Если число р—простое, а к—неотрицательное целое, мень­ шее р, то (£)=0 (mod р).

Указание. Предварительно показать, что р не делит /с!.

108. Индукцией по а доказать малую теорему Ферма.

Указание. Использовать равенство а^р = (1 + (а - 1))^р и предыдущую за­дачу.

109. Имеет место следующая китайская теорема об остатках: пусть к_ък₂,...,к_п—взаимно простые натуральные числа (моду­ ли); тогда для любых Ъ_ъ Ъ₂,..., Ъ_п е Z найдется /eN такое, что / = = b; (mod ki), i = 1, 2,..., п. (Задача восстановления числа по остаткам обсуждалась в древних китайских математических трактатах.) Дать конструктивное доказательство этой теоремы, т. е. доказательство, содержащее в себе алгоритм построения подходящего / (каждый такой алгоритм может быть назван китайским алгоритмом).

Указание. Пусть k = k₁k₂...k_n и g; = fc/fc;, i = l,2,...,n. При всех i = l,2, ... ..., п числа fc; и g_; взаимно просты, поэтому расширенным алгоритмом Евкли-

п

да можно определить h_{ так, что h_;g_; = 1 (mod fc_;) и положить /= Xi ^j^jSj.

110. Исходя из того, что значение полинома /(х) в точке х = а равно по теореме Безу остатку от деления /(х) на х-а, установить параллелизм между интерполяционной формулой Лагранжа и форму­ лой для значения /, данной в указании к задаче 109.

111. Битовая сложность китайского алгоритма, эскизно обрисован­ ного в указании к задаче 109 и основывающегося на расширенном алгоритме Евклида, наивном делении и наивном умножении, допус­ кает оценку 0(log²fc), если в качестве размера входа рассмотреть к, и оценку 0{т²), если в качестве размера входа рассмотреть битовую длину т числа к.

Указание. По поводу сложности вычисления g см. пример 20.2; сложность этапа вычисления всех g_; допускает оценку ОI J] log g log кЛ и т. д.

156