В преддверии старта базового кура "Математика для Data Science" приглашаем вас записаться на бесплатный демо-урок, который проведут наши эксперты.

А прямо сейчас предлагаем перевод полезной статьи.

Наивное вычисление знаменитой последовательности Фибоначчи производится за экспоненциальное время. Большинство людей могут сообразить, как сделать это за константное время. Но под силу ли нам улучшить этот показатель? Даже не сомневайтесь.

Что такое последовательность Фибоначчи?

Это классический бесконечный числовой ряд, в котором n-й член представляет собой сумму двух предыдущих членов. Первые два члена - 1 и 1. Третий - 2, четвертый - 3, затем следует 5, 8 и т. д.

Как это вычисляется обычно?

Чаще всего люди склонны использовать наивное рекурсивное решение, которое вызывает функцию на двух предыдущих членах. Очевидно, что это решение невероятно неэффективно, потому что выполняется за экспоненциальное время (каждый вызов функции разветвляется на два отдельных вызова для вычисления n-1 и n-2).

// calculates nth term of fibonacci, 1 indexed
Procedure Fib_Naive(int n):
    if(n < 3):
        return 1;
        end_if
    return Fib_Naive(n-1) + Fib_Naive(n-2)
end_Fib_Naive

Улучшенный подход

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

В качестве альтернативы мы могли бы просто использовать временную переменную (temp) и производить вычисления итеративно, что предпочтительнее, поскольку рекурсия обычно занимает больше времени, чем итерационные решения (потому что вызовы, помещаемые в стек, требуют дополнительных инструкций сборки кода).

// calculates nth term of fibonacci, 1 indexed
Procedure Fib(int n):
        if(n < 3): return 1;
        int prev = 1;
        int cur = 1;
        for i = 3...n:
            int temp = cur;
            cur += prev;
            prev = temp;
        end_for
return cur;
end_Fib

Новый подход

Прежде чем мы начнем, давайте слегка освежим базовые знания из линейной алгебры.

Вспомните единичную матрицу, по главной диагонали которой расположены единицы, а все остальные элементы равны нулю:

Если мы поменяем местами две строки единичной матрицы и умножим ее на другую матрицу, это будет эквивалентно перестановке тех же двух строк у другой матрицы:

Теперь предположим, что мы установили единицу в элемент в нижнем правом углу такой матрицы перестановок и умножили ее на вектор 2x1 (a, b). Что произойдет? По правилам умножения матриц, это поменяет местами первые две строки и сделает самый нижний элемент результирующего вектора равным (a + b).

Теперь мы можем вернуться к нашей задаче. Помните наше итеративное вычисление последовательности Фибоначчи? В этом уравнении a представляет предыдущий ((n-1)-й) элемент, а b представляет текущий.

Приведенное выше уравнение умножения матриц делает то же самое.

Оказывается, если мы возведем матрицу слева в n-ю степень и умножим ее на вектор (0, 1), мы получим n-й элемент последовательности Фибоначчи.

Откуда же логарифм?

Два слова: многократное квадрирование. Вместо того, чтобы умножать левую матрицу n раз, мы можем использовать предыдущие произведения умножения матриц, чтобы получить ответ быстрее.

Матрица, возведенная в 8-ю степень, может быть вычислена путем возведения в квадрат исходной матрицы, затем возведения в квадрат для достижения 4-й степени, а затем еще одного возведения в квадрат. Это быстрее, чем 8 раз умножать одну и ту же матрицу.

Таким образом, мы получаем следующий прогноз производительности:

В целях уменьшения путаницы, поскольку реализация на конкретном языке программирования может быть сложной, вот фактическая реализация на Java (а не псевдокод, как в предыдущих примерах).

Здесь нет матриц, но реализация все-равно использует преимущества многократного квадрирования, как обсуждалось ранее, для достижения искомой логарифмической производительности:

public int fib(int N) {
        if(N == 0) return 0;
        int[] sol = fibHelp(N);
        
        return sol[1];
    }
    
    public int[] fibHelp(int n) {
        if(n == 1) {
            return new int[] {0,1};
        }
        int m = n/2;
        
        int[] temp = fibHelp(m);
        
        int fPrev = temp[0];
        int fCur = temp[1];
        
        int prev = (fPrev * fPrev) + (fCur * fCur);
        int cur = fCur * (2 * fPrev + fCur);
        int next = prev + cur;
        
        if(n % 2 == 0) { 
            return new int[] {prev, cur};
        }
        else {
            return new int[] {cur, next};
        }
    }

*Примечание: Хотя может возникнуть соблазн сказать, что мы значительно сократили время вычислений и что сложность этой реализации может быть классифицирована как логарифмическая, все же есть один нюанс, который мы должны учитывать: временная сложность самой арифметики.

Самый быстрый из известных алгоритмов умножения выполняется за O(n log(n)). Технически количество арифметических операций не соответствует заявленному. Однако глубина нашей рекурсии логарифмическая, как видно из примера кода.

Записаться на открытый вебинар.