java - さまざまなフィボナッチ実装の Big-O

Question

フィボナッチ数列の n 番目の項を計算できるさまざまな手段のコードを (Java で) 実装しようとしましたが、学んだことを検証したいと思っています。

反復実装は次のとおりです。

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

これらの実装のビッグオーを理解しようとするとき、私は少し疑問を持っています。N-2回ループするため、反復実装はO（n）になると思います。

再帰関数では、再計算された値があるため、 O(n^2)だと思います。

メモ化された関数では、半分以上の値がメモ化に基づいてアクセスされます。問題の空間を一定の割合で減らすのに一定の時間がかかる場合、アルゴリズムは O(log N) であり、問​​題の空間を一定の量だけ減らすのに一定の時間がかかる場合、アルゴリズムは O(N) であると読みました。メモ化された実装の複雑さはO(n)であると私は信じていますか? もしそうなら、反復実装は 3 つすべての中で最良ではないでしょうか? （メモ化に必要な追加のメモリを使用しないため）。