Big-O для различных реализаций Фибоначчи

Question

Я просто попытался реализовать код (в Java) для различных способов, с помощью которых можно вычислить n-й член последовательности Фибоначчи, и я надеюсь проверить, что я узнал.

Итерационный реализация выглядит следующим образом:

public int iterativeFibonacci(int n) 
{ 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    int i = 0, j = 1, sum = 0; 
    for (; (n-2) != 0; --n) 
    { 
    sum = i + j; 
    i = j; 
    j = sum; 
    } 
    return sum; 
} 

Рекурсивная реализация выглядит следующим образом: -

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

memoized реализация выглядит следующим образом: -

public int memoizedFibonacci(int n) 
    { 
    if (n <= 0) return -1; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 
    if (memory[n-1] == 0) 
     memory[n-1] = memoizedFibonacci(n-1); 
    if (memory[n-2] == 0) 
     memory[n-2] = memoizedFibonacci(n-2); 
    return memory[n-1]+memory[n-2]; 
    } 

Я m, имея немного сомнений при попытке выяснить Big-O этих реализаций. Я считаю, что итеративная реализация должна быть O (n), поскольку она проходит через N-2 раза.

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

В memoized функции доступно более половины значений на основе memoization. Я читал, что алгоритм - это O (log N), если для уменьшения проблемного пространства требуется сокращение времени на долю, а - алгоритм O (N), если требуется постоянное время, чтобы уменьшить проблемное пространство на постоянное количество. Правильно ли я полагаю, что мемориальная реализация - O (n) по сложности? Если да, не будет ли итеративная реализация лучшей среди всех трех? (так как он не использует дополнительную память, требуемую памятью).

Answer 1

Рекурсивная версия не является полиномиальным временем - она ​​экспоненциальна, tightly bounded at φⁿ где φ - золотое соотношение (≈ 1.618034). Рекурсивная версия будет использовать O (n) память (использование происходит из стека).

версия мемоизации будет принимать O (п) времени при первом запуске, так как каждое число только вычисляется один раз. Однако взамен требуется O (n) память для вашей текущей реализации (n происходит от хранения вычисленного значения, а также для стека при первом запуске). Если запустить его много раз, временная сложность станет O (M + д) где M является максами все входного п и д этого число запросов. Сложность памяти станет O (M), который поступает из массива, который содержит все вычисленные значения.

Итерационный реализация является наилучшим, если вы считаете, один проход, так как он также работает в O (п), но использует постоянное количество памяти O (1) для вычисления. Для большого количества прогонов он будет пересчитывать все, поэтому его производительность может быть не такой хорошей, как версия memoization.

(Однако, практически говоря, задолго до проблемы производительности и памяти число, вероятно, переполняет даже 64-битное целое число, поэтому при точном анализе необходимо учитывать время, необходимое для выполнения добавления, если вы вычисляете полный номер).

Как уже упоминалось plesiv, число Фибоначчи также могут быть вычислены в O (войти п) путем матричного умножения (используя тот же прием, как быстро путем возведения в степень вдвое экспоненту на каждом шагу).