[알고리즘] Prologue - Recurrence relation, master theorm

1. 점화식 표현

  → 수열의 어떠한 항을 표현할 때, 그 이전의 항들을 활용하는 것

 Ex) 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, ...

  → f(n) = f(n-1) + f(n-2)

  → 위와 같은 표현을 '점화식 표현'이라 한다.

 

2. Master theorm

3. Fibonacci  sequence

   → 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

● 구현

(1) recursive call 방식

#include <stdio.h>

int Fibonacci(int n) {
	if (n == 0 || n == 1)	//degenerate_case
		return n;
	else
		return Fibonacci(n - 1) + Fibonacci(n - 2);
}

(2) 배열+반복문 활용 방식(재귀X)

#include <stdio.h>

int Fibonacci(int n) {
	int Fibo[100];
	Fibo[0] = 0;
	Fibo[1] = 1;

	for (int i = 2; i <= n; i++)
		Fibo[i] = Fibo[i - 1] + Fibo[i - 2];

	return Fibo[n];
}

● 성능

	(1) 재귀함수	(2) 배열+반복문
점화식 T(n)	T(n-1)+T(n-2)+k	T(n-1)
Master theorm 계산	O(2^n)	O(n)

  → 재귀함수보다 배열과 반복문을 활용하는 것이 더 효율적이다.

(* k: degenerate case)