November 29, 2021

Topic key words

Part 1. Memoization

Part 2. Tabulation

fibonacci

const fib = (n) => {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}

console.log(fib(50)); //시간 복잡도가 너무 높아서 계산을 못한다

만약 7을 구한다고 생각했을때 (top-down)

easy example 1

const dib = (n) => {
	if (n <= 1) return;
	dib(n - 1);
	dib(n - 1);
};

//O(2^n)time, O(n)space

easy example 2

const lib = (n) => {
	if (n <= 1) return;
	dib(n - 2);
	dib(n - 2);
};

//O(2^n)time, O(n)space