피보나치 수열 리트코드

3802 단어

제목


함수를 쓰고 n을 입력하여 피보나치(Fibonacci) 수열의 n항을 구합니다.피보나치 수열의 정의는 다음과 같다. f(n)= f(n-1)+f(n-2);

귀속 해법

int fib(int n)
{
	if(n<==0)
	{
		return 0;
	}
	if(n==1)
	{
		return n;
	}
	return fib(n-1)+fib(n+2);
}

이 귀환의 시간 효율은 지수급으로 효율이 매우 낮다.

낮게 올라가다


f(n) = f(n-1) + f(n-2); 
int dp[n+1];
dp[0] =0;
dp[1] = 1;
for(int i=2;i<=n;i++)
{
	dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];

낮은 방법에서 위로 올라가는 시간 효율은 O(n)이고 공간 효율은 O(n)이다.

더 빠른 효율 매트릭스 곱셈


시간 효율은 O(logn)이다.
외부 사이트의'js 태그 삽입'을 만들 때 주의해야 할 것
빠른 정렬 및 최적화

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage