Временная сложность алгоритма Фибоначчи

Итак, у меня есть рекурсивный метод в Java для получения n-го числа Фибоначчи. Единственный вопрос, который у меня есть: какова временная сложность? Я думаю, что это O (2 ^ n), но я могу ошибаться? (Я знаю, что итеративность лучше, но это упражнение)

public int fibonacciRecursive(int n)
{
    if(n == 1 || n == 2) return 1;
    else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}

java methods recursion time-complexity fibonacci
person Koeneuze    schedule 22.01.2011    source источник
comment
«Итеративность лучше» в целом неверна. Это правда, что она превосходит вашу наивную рекурсивную реализацию, но эту реализацию можно улучшить, чтобы она была практически на одном уровне с итеративной реализацией с использованием динамического программирования.   -  person Konrad Rudolph    schedule 22.01.2011

Ответы (5)


arrow_upward
5
arrow_downward

Ваш рекурсивный код имеет экспоненциальное время выполнения. Но я не думаю, что основание равно 2, а, вероятно, золотое сечение (около 1,62). Но, конечно, O (1.62 ^ n) тоже автоматически O (2 ^ n).

Время выполнения можно рассчитать рекурсивно:

t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1

Это очень похоже на рекурсивное определение самих чисел Фибоначчи. +1 в рекурсивном уравнении, вероятно, не имеет значения для больших n. Я считаю, что оно растет примерно так же быстро, как числа Фибона, а они растут экспоненциально с золотым сечением в качестве основы.

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

Ваш итеративный код имеет время выполнения O (n)

У вас есть простой цикл с O (n) шагами и постоянным временем для каждой итерации.

person CodesInChaos    schedule 22.01.2011
comment
Ааа, извините, я разместил неправильный код. Мне нужен был рекурсивный! Мой плохой, через сек отредактирую. - person Koeneuze; 22.01.2011
comment
@lars Вот почему я написал Но, конечно, O (1.62) тоже автоматически O (2). Но все же интересно узнать более близкую верхнюю границу, чем 2 ^ n. - person CodesInChaos; 22.01.2011
comment
O (???? ^ n) = O (2 ^ n) не следует напрямую из O (????) = O (2), поскольку O (n ^ ????)! = O (n²). Мне это не особенно интересно, поскольку для этой проблемы существует алгоритм O (lg n) (O (n) по количеству битов). - person Fred Foo; 22.01.2011
comment
@lars извините, это была опечатка. Я хотел написать O(1.62^n) автоматически O(2^n), но забыл ^n - person CodesInChaos; 22.01.2011

arrow_upward
5
arrow_downward

Вы можете использовать это

alt text

для вычисления Fn за O (log n)

person lacungus    schedule 22.01.2011

arrow_upward
3
arrow_downward

Каждый вызов функции выполняет ровно одно добавление или возвращает 1. Базовые случаи возвращают только значение один, поэтому общее количество добавлений равно fib (n) -1. Таким образом, общее количество вызовов функций равно 2 * fib (n) -1, поэтому временная сложность равна Θ (fib (N)) = Θ (phi ^ N), что ограничено O (2 ^ N).

person Nabb    schedule 22.01.2011

arrow_upward
0
arrow_downward

О (2 ^ п)? Я вижу здесь только O (n).

Интересно, почему вы продолжаете вычислять и пересчитывать их? Разве кеширование тех, которые у вас есть, не было бы хорошей идеей, если бы требования к памяти не стали слишком одиозными?

Поскольку они не меняются, я бы сгенерировал таблицу и сделал бы поиск, если для меня важна скорость.

person duffymo    schedule 22.01.2011

arrow_upward
0
arrow_downward

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

person Peter Taylor    schedule 22.01.2011
comment
Нет, чуть выше. Например, Fibo (2) имеет 3 вызова, но возвращает 2. Но для больших n разница не имеет большого значения. - person CodesInChaos; 22.01.2011