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 ) O( n ) 거듭제곱 O( n ) O( log n ) 피보나치 O( n ) O( 2**n )
int fib_iter(int n) { if(n==0) return 0; if(n==1) return 1; int pp=0; int p=1; int result=0; for(int i=2 ; i
int power(double x, int n) { if(n==0) return 1; else if((n%2) == 0) return power(x*x, n/2); else return (x * power( x*x, (n-1)/2 ); } * 시간복잡도 * O( log n )
int slow_power(double x, int n) { int i; double result = 1.0; for( i = 0 ; i < n ; i++ ) result *= x; return (result); } * 시간복잡도 * O(n) 반복으로 거듭제곱을 표현할 경우 순환보다 느리다
