509. Fibonacci Number (해석 + 풀이)

조건:

• 0 <= n <= 30

의역: 피보나치 수를 반환하라 

피보나치 수: 제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다.

출처: 나무위키

 

풀이:1. 반복문 사용

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    public int fib(int n) {
        if(n==0||n==1) return n;
        int first = 0;
        int second = 1;
        int thAns=0;
        for(int i=0;i<n-2;i++){
            thAns = first+second;
            first = second;
            second = thAns;
        }

        return thAns;
    }
}

2. 재귀 사용

class Solution {
    // 시간 복잡도 O(2^n) 공간 복잡도 O(n)
    public int fibRecursive(int n){
        if(n==0||n==1) return n;

        int fnm1 = fibRecursive(n-1);
        int fnm2 = fibRecursive(n-2);

        return fnm1+fnm2;
    }
}

재귀 함수의 시간복잡도에 관한 다른 설명 영상: https://www.youtube.com/watch?v=VcCkPrGaKrs 

fibRecursive 함수 자체의 시간 복잡도를 T(n) 라고 가정 할 때 T(n) = T(n-1) + T(n-2) -> 2T(n-1) 

T(n) = 2 * T(n-1) <근사치>

2 * T(n-1) = 2^2 * T(n-2)  <n -> n-1 대입>

... 반복

2^n-2 * T(2) = 2^n-1 * T(1) 이때 T(1)은 O(1) 임으로

T(2) = 2 (해당 과정 반복)

2^n-3 * T(3) = 2^n-2 * T(2) -> 2^n-2 * 2 -> 2^n-1

T(3) = 2^2

2^n-4 * T(4) = 2^n-3 * T(3) -> 2^n-3 * 2^2 -> 2^n-1

T(4) = 2^3

...

T(n) = 2^n-1 <근사치> -> 2^n

따라서 시간 복잡도는 O(2^n)

3. 동적 프로그래밍 DP

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int fibDp(int n){
        return fibDp(n,new int[n]);
    }
    public int fibDp2(int n){
        int fb[] = new int[n+1];
        fb[0] = 0;
        fb[1] = 1;
        for(int i=2;i<fb.length;i++)
            fb[i] = fb[i-1]+fb[i-2];
        return fb[n];
    }
}

4. 추후 업데이트 2차원 배열을 이용하여 O(log n)의 시간 복잡도 

class Solution2 {
    //**Time:O(logn)**  //(matrix size is 2*2(constant) so multiplication of matrix will take 2^3
    // time 8 which is constant. overall  Time compexity  :8logn which is Big O(logn) )
    //**Space :O(1)**//constant space (matrix size is fix 2*2 so space is constant)
    public int fib(int N) {
        if(N==0) return 0;
        int[][] matrix={{1,1,},{1,0}};

        int[][] identity={{1,0,},{0,1}};
        while(N!=1){
            if((N&1)!=0){
                identity=multiplication(matrix,identity);
                N--;
            }
            matrix=multiplication(matrix,matrix);
            N>>=1;
        }
        matrix=multiplication(matrix,identity);

        return matrix[1][0];
    }

    public static int[][] multiplication(int[][] matrix,int[][] res){
        int[][] ans=new int[2][2];

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix.length;j++){

                for(int k=0;k<matrix.length;k++){
                    ans[i][j]+=matrix[i][k]*res[k][j];
                }

            }
        }
        return ans;
    }
}

 

<메모>

피보나치 수를 구하는 코드 중 가장 빠른 시간 복잡도는 O(log n)이다.