java - 표기법 - 알고리즘 시간 복잡도 정리




다양한 피보나치 구현을위한 Big-O (2)

필자는 피보나치 시퀀스의 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를 알아 내려고 할 때 조금 의심 스럽습니다. 나는 N-2 회 반복하면서 O (n) 반복 구현을 믿습니다.

재귀 함수에서 값이 다시 계산되므로 O (n ^ 2) 라고 생각합니다.

메모 기능을 사용하면 메모를 기반으로 값의 절반 이상이 액세스됩니다. 나는 문제 공간을 일정하게 줄이기 위해 일정 시간이 걸리고, 일정한 양만큼 문제 공간을 줄이기 위해 일정 시간이 걸리는 경우 알고리즘이 O (N) 인 알고리즘을 O (log N)이라고 읽었습니다. 기억 된 구현이 복잡성에서 O (n) 라고 믿는 것이 맞습니까? 그렇다면 반복 구현이 세 가지 중에서 가장 좋지 않을까요? (메모 작성에 필요한 추가 메모리를 사용하지 않으므로).


재귀 버전은 다항식 시간이 아닙니다. 지수가 지수 함수이므로 φ가 황금 비율 (≈ 1.618034) 인 φ n 에서 단단히 경계를 잡습니다. 재귀 버전은 O ( n ) 메모리를 사용합니다 (스택에서 사용량이옵니다).

메모 버전은 첫 번째 실행시 O ( n ) 시간이 소요됩니다. 각 숫자는 한 번만 계산되기 때문입니다. 그러나 현재의 구현을 위해 O ( n ) 메모리를 사용합니다 ( n 은 계산 된 값 저장과 첫 번째 실행시 스택에 대한 것임). 여러 번 실행하면 시간 복잡도는 O ( M + q )가되며 여기서 M 은 모든 입력 n 의 최대 값이고 q 는 쿼리 수입니다. 메모리 복잡성은 모든 계산 된 값을 보유하는 배열에서 오는 O ( M )이됩니다.

반복 구현은 O ( n )에서도 실행되지만 일정한 메모리 양 O (1)을 사용하여 하나의 실행을 고려하면 가장 좋습니다. 실행 횟수가 많으면 모든 것을 다시 계산하므로 성능은 메모 버전만큼 좋지 않을 수 있습니다.

(실제로 성능과 메모리의 문제가 있기 훨씬 전에 64 비트 정수에서도 숫자가 오버플로되기 쉽기 때문에 정확한 분석은 전체 숫자를 계산하는 경우 추가 작업을 수행하는 데 걸린 시간을 고려해야합니다) .

앞서 언급했듯이, 피보나치 수는 행렬 곱셈 (모든 단계에서 지수를 절반으로 나눔으로써 빠른 지수법과 같은 트릭을 사용)에 의해 O (log n )에서 계산 될 수 있습니다.


행렬 곱셈을 사용하여 피보나치 수를 찾는 Java 구현은 다음과 같습니다.

private static int fibonacci(int n)
{
    if(n <= 1)
        return n;

    int[][] f = new int[][]{{1,1},{1,0}};

    //for(int i = 2; i<=n;i++)
        power(f,n-1);

    return f[0][0];
}

// method to calculate power of the initial matrix (M = [][]{{1,1},{1,0}})

private static void power(int[][] f, int n)
{
    int[][] m = new int[][]{{1,1},{1,0}};

    for(int i = 2; i<= n; i++)
        multiply(f, m);


}

// method to multiply two matrices
private static void multiply(int[][] f, int[][] m)
{

    int x = f[0][0] * m[0][0] + f[0][1] * m[1][0];
    int y = f[0][0] * m[0][1] + f[0][1] * m[1][1];
    int z = f[1][0] * m[0][0] + f[1][1] * m[1][0];
    int w = f[1][0] * m[0][1] + f[1][1] * m[1][1];

    f[0][0] = x;
    f[0][1] = y;
    f[1][0] = z;
    f[1][1] = w;



}

Fibonacci 수를 계산하는 Matrix 지수 방법보다 빠른 방법은 Fast Doubling method입니다. 두 방법의 상각 된 시간 복잡도는 O (logn)입니다. 이 방법은 다음의 공식을 따른다. F (n) = F (n) 2 F (n + 1) 2

Fast Doubling 메소드를 구현 한 Java 구현은 다음과 같습니다.

private static void fastDoubling(int n, int[] ans)
{
    int a, b,c,d;

    // base case
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }

    fastDoubling((n/2), ans);

    a = ans[0];  /* F(n) */
    b = ans[1];  /* F(n+1) */
    c = 2*b-a;

    if(c < 0)
        c += MOD;

    c = (a*c) % MOD;  /* F(2n)  */
    d = (a*a + b*b) % MOD ;  /*  F(2n+1) */

    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = (c+d);
    }

}






time-complexity