Решение упражнения 1.26 из SICP

12 October, 2007 (20:00) | Решения упражнений

Отличие реализации Хьюго в том, что на каждом шаге (expmod) для четного показателя степени вызывает себя с вдвое меньшим показателем не один раз, а два.

Пусть C(n) – число операций, необходимых для вычисления (expmod n exp m). Покажем, что для реализации Хьюго C(n) растет как линейная функция, а не логарифм.

Про алгоритм Хюго можно записать:

  1. C(2n) = 2 C(n) + A1, где A1– некая константа, не зависящая от n,
  2. C(2n+1) = C(2n) + A2, где A2 некая константа, не зависящая от n.
  3. С(0) = A3, где A3 некая константа, не зависящая от n.

Мы хотим показать, что для любого n выполняется соотношение (*) C(n) = C1n + C2, где C1 и C2 – константы.

Воспользуемся методом математической индукции.

В качестве базы индукции возьмем n=0. В этом случае соотношение (*) истинно в силу 3-го пункта описания алгоритма Хьюго.

Предположим, что для всех k от 0 до n-1 соотношение (*) выполняется и докажем его истинность при k=n. Рассмотрим отдельно случай нечетного и четного n.

Начнем с нечетного n = 2 m + 1. В этом случае по пункту 2 получаем:

С(n) = C(2m+1) = C(2m) + A2 =  2 C1 m + C2 + A2  (согласно индуктивного предположения, так как 2m < 2m+1 = n) =  C1 (2m+1) + (C+ A2 – C1) = C1n + (C+ A2 – C1)  – получили требуемый линейный вид.

Теперь перейдем к случаю четного  n = 2 m. Для этого случая по пункту 1 получаем:

C(n) = C(2m) = 2 C(m) + A1 = 2 (C1m + C2) + A1 (согласно индуктивного предположения, так как m < 2m = n) =  C12m + (2C2 + A1)  =  C1n + (2C2 + A1)  – вновь получили линейный вид, к которому стремились.

Таким образом, согласно принципу математической индукции, мы доказали, что процесс, порождаемый процедурой Хьюго, имеет порядок Θ(n), а не Θ(log n).

Хьюго стоит хорошо подумать о вреде дублирования кода.

Write a comment