피보나치 수열 구해

피보나치 수열의 정의는 다음과 같다.
n=0일 때 F[n]=0;
n=1일 때 F[n]=1;
n>1일 때 F[n]=F[n-1]+F[n-2];
해법1(동적 기획 사상):
 

int Fib(int n)

{

    int pre1=1;

    int pre2=0;

    if(n==0)

        return 0;

    if(n==1)

        return 1;

    for(int i=2;i<=n;i++)

   {

        result=pre1+pre2;

        pre2=pre1;

        pre1=result;

   }

   return result;

}

 
시간의 복잡도는 O(n)이다.
해법2: 분치 전략
(F(n),F(n-1))=(F(n-1),F(n-2))*A=...=(F(1),F(0))*A^(n-1);
A={{1,1},{1,0}};
행렬 A의 멱으로 전환하다.
코드는 다음과 같습니다.
 

#include<iostream>

using namespace std;

class Matrix2

{

public:

	Matrix2(int a1,int a2,int b1,int b2)

	{

		m11=a1;

		m12=a2;

		m21=b1;

		m22=b2;

	}

	int getm11()const

	{

		return m11;

	}

	int getm12()const

	{

		return m12;

	}

	int getm21()const

	{

		return m21;

	}

	int getm22()const

	{

		return m22;

	}

private:

	int m11;

	int m12;

	int m21;

	int m22;

};

Matrix2 MatrixPow(const Matrix2& m,int n);

int Fib(int n);

int main()

{

	int n;

	cin>>n;

	cout<<Fib(n)<<endl;

	return 0;

}

Matrix2 matmultiply(const Matrix2& mat1,const Matrix2& mat2)

{

	int m11=mat1.getm11()*mat2.getm11()+mat1.getm12()*mat2.getm21();

	int m12=mat1.getm11()*mat2.getm12()+mat1.getm12()*mat2.getm22();

	int m21=mat1.getm21()*mat2.getm11()+mat1.getm22()*mat2.getm21();

	int m22=mat1.getm21()*mat2.getm12()+mat1.getm22()*mat2.getm22();

	return Matrix2(m11,m12,m21,m22);

}

Matrix2 MatrixPow(const Matrix2& mat,int n)

{

	Matrix2 result(1,0,1,0);

	Matrix2 tmp=mat;

	for(; n; n>>=1)

	{

		if(n&1)

			result=matmultiply(result,tmp);

		tmp=matmultiply(tmp,tmp);

	}

	return result;

}

int Fib(int n)

{

	if(n==0)

		return 0;

	else if(n==1)

		return 1;

	Matrix2 mat(1,1,1,0);

	Matrix2 an=MatrixPow(mat,n-1);

	return an.getm11();

}

시간의 복잡도는 O(nlogn)이다.