피보나치수열,정렬의 실행시간분석

저번에 공부한 코드실행시간분석 코드를 이용해 피보나치수열을

반복, dp(동적프로그래밍)으로 성능차이를 분석해보겠습니다.

재귀함수로 구현한 피보나치는 O(2^N)이고

dp로 구현한 피보나치는O(N)으로, 재귀로구현한것보다 훨씬!!빠른 효율적인 알고리즘입니다.

반복문으로구현한 피보나치또한 O(N)입니다.

따라서 범위가 작을때는 어느방법을 사용해도상관없으나 범위가 커질수록  효율적인 방법을 써야합니다.

dp와 반복문으로로구한 피보나치수열의 시간차이가 상당함을 알 수 있습니다.

(상당한 차이입니다.)

빅오표기법으로 표기한 4가지 시간복잡도의 빠른순서(왼쪽부터)

O(N) <O(NlogN) <O(N^2) < O(2^N)

#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
int fibo_recursive(int x);
int fibo_dp(int x);
int  fibo_repeat(int x);
int  dp[100];
int main()
{
	clock_t start, finish;
	double duration;
	int sum = 0;
	start = clock();
	int x = fibo_recursive(40);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "재귀구현피보나치값:" << x << "시간: " << duration << "초\n";

	start = clock();
	int y = fibo_dp(40);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "dp구현피보나치값:" << y << "시간: " << duration << "초\n";

	start = clock();
	int z = fibo_repeat(40);
	finish = clock();
	cout << "반복문피보나치값:" << z << "시간: " << duration << "초\n";
}
int fibo_recursive(int x)
{

	if (x == 1)return 1;
	if (x == 2)return 1;
	return fibo_recursive(x - 1) + fibo_recursive(x - 2);
}
int fibo_dp(int x)
{
	if (x == 1)return 1;
	if (x == 2)return 1;
	if (dp[x] != 0)return dp[x];
	return dp[x] = fibo_dp(x - 1) + fibo_dp(x - 2);
}
int  fibo_repeat(int x)
{
	if (x == 1)return 1;
	if (x == 2)return 1;
	int temp, current = 1, last = 0;
	for (int i = 2; i <= x; i++)
	{
		temp = current;
		current += last;
		last = temp;
	}
	return current;
}