다양한 피보나치 수열 알고리즘

이번 알고리즘 과제 중에 변형 피보나치 수열 알고리즘이 나왔는데 과제를 풀면서 찾아보니 생각보다 피보나치 수열 알고리즘이 다양했다. 정리도 할 겸 올려놓는다.

피보나치 수열의 점화식은 다음과 같다.

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2)

ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

참고로 과제 문제로 나왔던 변형 피보나치 수열의 점화식은 F(0) = F(1) = 1, F(n) = F(n - 1) + F(n - 2) + 1이었다.

시간복잡도가 지수 함수인 재귀 알고리즘

long long fibo1(int n)
{
	if (n < 2)
	{
		return n;
	}
	else
	{
		return fibo1(n - 1) + fibo1(n - 2);
	}
}

가장 기초 중의 기초인 재귀 함수를 이용한 피보나치 수열 함수이다. 다들 알다시피 중복으로 호출되는 함수가 많아서 굉장히 비효율적이다. 시간복잡도는 대략 O(2^n)

시간복잡도가 선형인 반복 알고리즘

long long fibo2(int n)
{
	long long a = 0, b = 1;
	long long c = a + b;
	if (n < 2)
	{
		return n;
	}
	else
	{
		for (int i = 2; i < n; i++)
		{
			a = b;
			b = c;
			c = a + b;
		}
		return c;
	}
}

위 재귀 알고리즘을 반복문으로 고친 것이다. 시간복잡도는 O(n)

시간복잡도가 선형인 재귀 알고리즘

long long a[100] = { 0, 1 };
long long fibo3(int n)
{
	if (n < 2 || a[n] != 0)
	{
		return a[n];
	}
	else
	{
		a[n] = fibo3(n - 1) + fibo3(n - 2);
		return a[n];
	}
}

이전 재귀 알고리즘이 비효율적인 이유는 이미 계산한 부분을 중복으로 호출하기 때문이다. 따라서 이미 계산한 부분을 다른 곳에 저장해놨다가 필요할 때 꺼내쓰면 재귀문으로도 반복문급 속도를 낼 수 있다. 시간복잡도가 O(n)

이 기법을 메모이제이션이라 한다. 시간복잡도와 공간복잡도를 등가 교환한 셈이지만 전역변수의 특성상 함수 종료 후에도 저장되어 있으므로 함수를 여러 번 호출한다면 위 반복문 코드보다 나을 수 있다.

시간복잡도가 로그 함수인 알고리즘

typedef vector< vector<long long> > matrix;

matrix operator *(const matrix &a, const matrix &b)
{
	int n = a.size();
	matrix c(n, vector<long long>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				c[i][j] += a[i][k] * b[k][j];
			}
		}
	}
	return c;
}

long long fibo4(int n)
{
	vector<long long> tmp(2);
	matrix a;
	tmp[0] = 1;
	tmp[1] = 1;
	a.push_back(tmp);
	tmp[0] = 1;
	tmp[1] = 0;
	a.push_back(tmp);
	matrix b;
	tmp[0] = 1;
	tmp[1] = 0;
	b.push_back(tmp);
	tmp[0] = 0;
	tmp[1] = 1;
	b.push_back(tmp);

	if (n < 2)
	{
		return n;
	}
	else
	{
		for (; n > 0; n /= 2)
		{
			if (n & 1 == 1)
			{
				b = b * a;
			}
			a = a * a;
		}
		return b[0][1];
	}
}

사실 이 글을 쓰게 된 이유이다. 행렬곱을 이용한 방법인데 시간복잡도가 O(log n)이다. ㄷㄷ vector를 사용했기 때문에 C++에서 vector 헤더 파일이 필요하다.

피보나치 수열을 행렬로 나타내고 정리하면 다음과 같다.

결국, 행렬의 n 제곱을 계산해야 하는데 어떤 수의 n 제곱을 log n 시간에 구하는 알고리즘이 있다. 나도 그냥 가져다 쓰거라 완벽하게 이해한 건 아니지만 간단하게 설명하자면 2^32를 구한다고 했을 때 2*2*2*2*... 이런 식으로 구하는 게 아니라 2를 제곱해서 2^2을 구하고 다시 제곱해서 2^4를 구하고 다시 제곱해서 2^8을 구하는 식으로 계산하는 것이다. 계산 과정이 32에서 log_2 32로 줄어든다.

일반항을 이용한 알고리즘

long long fibo5(int n)
{
	double sqrt5 = sqrt(5);
	return 1 / sqrt5 * (pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n));
}

이건 그냥 알려진 피보나치 수열의 일반항을 이용해 푸는 것이다. 사실 일반항이 있다는 것도 검색하다가 알게 되었다. sqrt와 pow 함수를 사용했기 때문에 C에서 math.h, C++에서 cmath 헤더 파일이 필요하다.

피보나치 수열의 일반항은 아래와 같다.

sqrt와 pow 함수의 시간복잡도를 모르기 때문에 정확한 시간복잡도는 모르겠지만 아마 가장 빠르지 않을까 싶다.