자료구조 2(순환 1)

---

- 순환

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

-> 즉 재귀 함수를 뜻함

사용 경우 : 팩토리얼의 순환/ 하노이탑

하지만 일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행 속도 면에서는 떨어진다. 따라서 알고리즘을 설명할 때만 순환으로 하고 실제 프로그램에서는 그것을 반복 버전으로 바꾸어 코딩하는 경우도 있음

---

- 순환의 원리

문제의 일부를 해결한 다음 나머지 문제에 대하여 순환호출을 한다.

주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법을 분할정복 이라 한다.

순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리한 방법이다.

---

- 순환 알고리즘의 성능

반복 알고리즘과 순환 알고리즘이 단순한 시간 복잡도는 같지만 순환 호출의 경우 여분의 기억공간이 더 필요하고 함수를 호출하기 위해서는 함수의 매개변수들을 스택에 저장하는 것과 같은 사전작업이 필요하기 때문에 수행 시간이 더 걸리게 된다.

---

- 순환알고리즘은 모든 경우에서 반복 알고리즘보다 느린가?

 

팩토리얼 계산 프로그램에서는 반복적인 방법이 순환보다 속도가 빠르다 하지만 숫자 x의 n-거듭제곱값인 xn을 구하는 함수를 작성한다면

 

-반복적인 알고리즘-

double iterative_power(double x, int n) {
	
    int i;
    double result = 1.0;
    
    for(i = 0; i < n; i++)
    	result *= x;
  	
    return result;
}

 

-순환적인 알고리즘-

double recursion_power(double x, int n) {
	
    if(n == 0)
		return 1;
        
    else if (n %2 == 0)
    	return recursion_power(x*x, n/2);
        
    else
    	return x*recursion_power(x*x, (n-1)/2);
 }

이런 식으로 코드를 작성할 수 있다.

 

보기에는 순환적인 알고리즘이 시간이 더 걸릴 것 같지만 순환적인 알고리즘이 더 빠르다 그 이유는 한 번의 순환을 할 때마다 문제의 크기가 약 절반으로 줄어들기 때문이다. n을 100이라고 치고 생각해보면

$$100 → 50 → 25 → 12 → 6 → 3 → 1$$

n을 2의 거듭제곱인 2k라고 가정한다면

$$2^k → 2^k-1 → 2^k-2 → ... → 2^1 → 2^0$$

즉 k번의 순환호출이 일어나는 것을 확인할 수 있다.

그렇기 때문에 순환호출의 시간 복잡도는 O(log2n)이 되고 반복 알고리즘의 시간 복잡도는 O(n)이다.

 

따라서 무조건적으로 순환알고리즘이 반복적인 알고리즘보다 느린 것은 아니며 코드를 작성할 때 어떤 방식으로 코드가 작동하는지 생각해보고 순환 알고리즘을 사용할 것인지 반복 알고리즘을 사용할 것인지 생각해봐야 한다.

---