프로그래머스[Java] - (Level2)피보나치 수(재귀 , 비재귀DP)

https://programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

코드1(비재귀, DP)

class Solution {

  public int solution(int n) {
      int[] arr = new int[100001];
      arr[1] = 1;
      arr[2] = 1;
      for(int i=3; i<=n; i++)
          arr[i] = (arr[i-2] + arr[i-1]) % 1234567;
      return arr[n];
  }
}

풀이

 

 

코드2(재귀)

class Solution {
  public static int fibo(int n){
      if(n<=1)
          return n;
      else  
          return (fibo(n-2) + fibo(n-1)) % 1234567;
  }

  public int solution(int n) {
      int answer = fibo(n);
      return answer;
  }
}

 

 

https://gam0za.tistory.com/4

재귀를 이용한 방식은 호출 한번당 2배씩(F(n) = F(n-2) + F(n-1)) 늘어나게 되고, 총 n단계 이므로

BigO(2^N) 이다. 

주어진 n의 범위는 100000이하인데, 2^100000은 당연히 시간초과가 발생한다.

2^30만 해도 10억,

 

 

비재귀(DP)를 이용한 방식의 시간 복잡도는 BigO(N) 이다.