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

Я просто попытался реализовать код (в 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);
  }

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

  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];
  }

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

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

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

Ответ 1

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

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

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

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

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