[개념] 피보나치 수열 알고리즘

피보나치 수열 알고리즘

(1) 재귀(recursion)

(2) 동적 프로그래밍(Dynamic Programming)

(3) 반복(For문)

피보나치 수열의 BigO()는 방식에 따라 다름.

(1) 재귀: BigO(2^n)

(2) 동적: BigO(n^2)

(3) 반복: BigO(n)

 

 안정성 문제로 가장 좋은 방법은 바로 반복이다. 

 

import java.util.Scanner;
public class Pibo {
          Scanner s = new Scanner(System.in);
          System.out.print("정수 입력 : ");
          int j=s.nextInt();
          
          int num1,num2,sum;
          num1=0; // 첫번째와 두번째 값이 1이어야 하므로 초기값을 0과
          num2=1; // 1로 준다
          sum=1; // 첫번째 1은 그냥 초기값으로 설정
          
          for(int i=0; i<j; i++)
          {
              System.out.print(sum+" ");
              sum=num1+num2; // 두 값을 더한 후
              num1=num2;
              num2=sum; // 두번째 연산자에 더한 값을 넣어준다.
          }

     }
}

 

 

 

출처 - https://makefortune2.tistory.com/60