[알고리즘] log n의 시간복잡도를 갖는 피보나치 코드 (c언어 소스, 증명 및 예제)

소개글

[알고리즘] log n의 시간복잡도를 갖는 피보나치 코드 (c언어 소스, 증명 및 예제)

증명 및 소스코드, 예제를 포함한 문서입니다.

목차

없음

본문내용

➤ 소개

다시 돌아온 피보나치 - -

누구나 이해 할 수 있게 쉽게 풀어쓴 자료입니다.

본 자료는 직접 본인이 만들었으며, 과제 점수 만점을 받은 자료입니다.

<중략>

C언어 코드
#include <stdio.h>

long n, out[2][2], input[2][2]={{0,1},{1,1}}, base[2][2]={{0,1},{1,1}};

int count=0;



void fib(int ex) //재귀 함수
{
if(ex%2==0)
{
if(ex/2!=1) fib(ex/2);
//2로 나누어지는 경우 제곱한 뒤 다시 저장
out[0][0] = input[0][0]*input[0][0]+input[0][1]*input[1][0];
out[0][1] = input[0][0]*input[0][1]+input[0][1]*input[1][1];
out[1][0] = input[1][0]*input[0][0]+input[1][1]*input[1][0];
out[1][1] = input[1][0]*input[0][1]+input[1][1]*input[1][1];
count++;
//단위 연산이 몇 번 실행되나 확인
input[0][0] = out[0][0];
input[0][1] = out[0][1];
input[1][0] = out[1][0];
input[1][1] = out[1][1];
}//배열 out에 임시로 저장한 값을 배열 input에 다시 넣음

<중략>

참고 자료

없음