피보나치 수열 (반복구조), (순환구조)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


int main(void)
{
	int n;
	
	int a, b, c;
	a = 0;
	b = 1;
	c = 1;

	printf("몇번째 항까지 구할까요?: ");
	scanf("%d", &n);
	for (int i = 0; i <= n; i++) {
		printf("%d, ", a);
		c = a + b;
		a = b;
		b = c;
	}
	return 0;
}

반복구조

 

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

순환구조

반복구조가 더 시간복잡도 측면에서 효율적이다.

순환구조는 O(2^n)인 반면 반복구조는 O(n)이다.