Вычисление n-го числа Фибоначчи - популярная задача, которая на практике почти не встречается, но часто прменяется в обучающих целях, а также на собеседованиях. Задача очень проста, но решить ее можно несколькими алгоритмами, причем время выполнения таких алгоритмов может сильно различаться между собой.

Понятие числа Фибоначчи:

Итак, простой пример последовательности Фибоначчи (каждое последующее число равно сумме двух предыдущих):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .

Рекуррентное соотношение таково:

F(0) = 0,
F(1) = 1,
F(i) = F(i−1) + F(i−2), где i >= 2.

Первый способ

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

1
2
3
4
5
6
7
8

    private static int fibonacci1(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;

        return fibonacci1(n - 1) + fibonacci1(n - 2);
    }

Это простой, но и самый неэффективный алгоритм, так как время алгоритма растет экспоненциально - O(2^n). Рекурсивное дерево вызовов выглядит следующим образом:

Второй способ

Второй способ основан на принципе с сохранением каждого предыдущего числа последовательности в массиве. Такой алгоритм требует уже линейное время - O(n) на выполнение и дополнительное количество памяти для хранения всего массива чисел - O(n):

1
2
3
4
5
6
7
8
9
10
11

    private static int fibonacci2(int n) {
        int[] a = new int[n+1];
        a[0] = 0;
        a[1] = 1;

        for (int i = 2; i <= n; i++) {
            a[i] = a[i-1] + a[i-2];
        }

        return a[n];
    }

Третий способ

Третий способ похож на первый, за исключением того, что, мы будем хранить не весь массив вычисленных чиел, а только предыдущие два. Таким образом, колчиство дополнительной памяти сократится до O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13

    private static int fibonacci3(int n) {
        int fPrev = 0;
        int fCurrent = 1;
        int fNext = 0;

        for (int i = 2; i <= n; i++) {
            fNext = fPrev + fCurrent;
            fPrev = fCurrent;
            fCurrent = fNext;
        }

        return fNext;
    }