Как вы помните, числа Фибоначчи определяются через суммирование предыдущих членов в ряду: каждое число равно сумме двух предыдущих, а первые два равны 1. Таким образом, получается ряд натуральных чисел { 1; 1; 2; 3; 5; 8; 13; 21; … }. Обозначим n-ный член этого ряда через F(n). Мы можем определить рекуррентную формулу для F(n):
F(n) = F(n − 1) + F(n − 2)
F(1) = F(2) = 1
Попытка применить эту формулу для практического вычисления неэффективна до нелепости: например, чтобы вычислить F(5), мы сначала вычислим F(4) и F(3), a вычисляя F(4), мы должны вычислить F(3) и F(2). F(3) уже вычисляется дважды. Легко видеть, что при вычислении для больших n число повторов растет, будто лавина.
Естественно упростить вычисление, двигаясь от начала ряда. Если мы каждый раз будем помнить только 2 числа в их порядке, по ним мы можем вычислить третье, «забыть» первое — оно больше не нужно — и повторять эту операцию с оставшимися двумя, пока не сделаем нужного числа шагов. Этот метод гарантирует вычисление F(n) за число шагов n−2, то есть, как об этом говорится, порядка n, и общепринято записывается как O(n).
Новое рекуррентное соотношение для F потребует введения вспомогательной функции, которая будет «помнить» два числа в своих аргументах. Третий аргумент нужен только, чтобы завершить вычисления, не забыть, где нам остановиться, идя вдоль ряда Фибоначчи: он задает число оставшихся шагов:
А теперь приходит добрый волшебник Хэл Абельсон и говорит: я знаю, как значительно ускорить это вычисление! Можно модифицировать алгоритм, чтобы «перескакивать» в ряду шагами, кратными 2n.
ψ (p, q) (a, b) → ψ (p, q) ((a + b)p + aq, ap + bq)
Хорошо видно, что
φ = ψ (1, 0)
Теперь аналитически применим функцию ψ дважды к данным a и b
Обратите внимание, что форма этого выражения соответствует однократному применению ψ, но только с иными значениями p и q:
p → p² + 2pq
q → p² + q²
Таким образом, рекуррентная самотождественность ψ сохранилась, и мы можем удваивать наши шаги каждый раз, когда обнаружим, что до нашего F(n) их остается четное число: просто заменим p и q на новые, соответствующие двойному шагу, и при этом вдвое уменьшим число оставшихся шагов. Полное решение можно записать так:
Очевидно, что перед каждым удвоенным шагом мы будем делать не более одного неудвоенного, так что число шагов будет падать вдвое на каждые не более двух сделанных, так что новый алгоритм вычисляет F(n) за логарифмическое число шагов O(log n).
А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?
Комментарии (0)