피보나치 수열

코드

class Main {
	
	static int stackFrame(int n){
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	
	public static void main(String[] args){
		int n=10;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println();
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println(Arrays.toString(intArr));
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		
	}

	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
}

---

결과

1 1 2 3 5 8 13 21 34 55 
총 소요 시간 : 242100
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
총 소요 시간 : 48000

 

---

단순 재귀 호출로는 값이 클 수록 매번 이전 값을 계산하느라 시간 소요가 기하급수적으로 증가한다.

반면에 배열은 이전 값을 재귀적으로 구하지 않으니 값 계산 속도는 선형적으로 증가한다.

import java.util.Arrays;

class Main {
	static int cnt = 0;
	
	static int stackFrame(int n){
		cnt++;
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	
	public static void main(String[] args){
		int n=45;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println();
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println(Arrays.toString(intArr));
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 반복 수 : "+cnt);
		
	}

	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			cnt++;
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
}

몇 번 호출되는지 카운트 해봤다.

 

 

재귀 호출로 매 번 계산은 비효율적이니 상태값을 저장할 배열을 생성해 적용해보자

import java.util.Arrays;

class Main {
	static int cnt = 0;
	static int[] stackArr;
	
	static int stackFrame(int n){
		cnt++;
		if(n<=2) return 1;
		else return stackFrame(n-2)	+stackFrame(n-1);
	}
	
	static int stackFramePlusArray(int n){
		cnt++;
		if(stackArr[n]>0) return stackArr[n];
		if(n<=2) return stackArr[n]=1;
		else return stackArr[n]=stackFramePlusArray(n-2)+stackFramePlusArray(n-1);
	}
	
	private static int[] useArray(int n) {
		int[] intArr = new int[n];
		for(int i=1; i<=n; i++) {
			cnt++;
			if(i<=2) {
				intArr[i-1] = 1;
			} else {
				intArr[i-1] = intArr[i-2]+intArr[i-3];
			}
		}
		return intArr;
	}	
	
	public static void main(String[] args){
		int n=45;
		
		long start = System.nanoTime();
		for(int i=1; i<=n; i++) System.out.print(Main.stackFrame(i)+" ");
		System.out.println("\n반복문 + 재귀");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		stackArr = new int[n+1];//인덱스 0자리 쓰기 싫어서 +1
		start = System.nanoTime();
		System.out.println("######################################");
		for(int i=1; i<=n; i++) System.out.print(Main.stackFramePlusArray(i)+" ");
		System.out.println("\n반복문 + 재귀(메모이제이션)");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		cnt=0;
		Arrays.fill(stackArr, 0);
		start = System.nanoTime();
		Main.stackFramePlusArray(n);
		System.out.println("######################################");
		System.out.print(Arrays.toString(stackArr));
		System.out.println("\n재귀(메모이제이션)");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 호출 수 : "+cnt);
		
		
		cnt=0;
		start = System.nanoTime();
		int[] intArr = useArray(n);
		System.out.println("######################################");
		System.out.println(Arrays.toString(intArr));
		System.out.println("반복문");
		System.out.println("총 소요 시간 : " + (System.nanoTime()-start));
		System.out.println("총 반복 수 : "+cnt);
		
	}

}

배열에 미리 계산된 값이 있다면, 더 이상 계산할 것 없이 그 값을 반환하도록 했다.