[파이썬] 자료구조 (1) 순환 알고리즘

순환 알고리즘

팩토리얼

• 순환적으로 구현한 팩토리얼

def factorial(n):
	if n == 1: return 1
    else: return n * factorial(n-1)

 

순환함수 => 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있음.
위의 시간복잡도 O(n)

• 반복 구조로 구현한 팩토리얼

def factorial(n):
	result = 1
    for k in range(n,0,-1):
    	result = result * k
    return result

시간복잡도 O(n)

순환은 트리와 같은 특정한 문제에 대해 반복에 비해 훨씬 명확하고 간결한 알고리즘을 나타내지만, 실행속도 면에서는 많은 경우 함수 호출의 부담에 의해 반복보다 느림.

• 순환 알고리즘은 이해하기 쉽다는 것과 쉽게 프로그래밍 할 수 있다는 장점
• but 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다

거듭제곱 (xn) 구하기

순환이 더 빠른 예
거듭제곱 구하기(xn 구하기)_ 순환 알고리즘 (O(logn))

def power(x, n):
	if n == 0:
    	return 1
    elif (n % 2) == 0:
    	return power(x*x, n//2) 
    else:
    	return x * power(x*x, (n-1)//2)

거듭제곱 구하기_반복 알고리즘 (O(n))

def power_iter(x,n):
	result = 1.0
    for i in range(n):
    	result = result * x
    return result

위의 거듭제곱 구하기를 보면 순환 구조를 사용했을 때 문제의 크기가 하나씩 줄어드는 게 아니라 절반씩 줄어들게 된다.

피보나치 수열

피보나치 수열 :​

순환이 더 느린 예
피보나치 수열의 계산

• 순환 알고리즘 (O(2n))

def fib(n):
	if n == 0: return 0
    elif n == 1: return 1
    else:
    	return fib(n-1) + fib(n-2)

• 반복 알고리즘 (O(n))

def fib_iter(n):
	if (n < 2): return n
    last = 0
    current = 1
    for i in range(2, n+1):
    	tmp = current
        current += last
        last = tmp
    return current

하노이의 탑

순환 알고리즘에서는 순환이 일어날수록 문제의 크기가 작아져야 한다
1. 먼저 위에 쌓여 있는 n-1개의 원판을 B로 옮긴다. C를 임시막대로 사용한다
2. 제일 밑에 있는 원판을 C로 옮긴다
3. B로 옮겨져 있는 n-1개의 원판을 C로 옮긴다. A를 임시막대로 사용한다

def hanoi_tower(n, fr, tmp, to): #하노이탑 순환함수
	if (n == 1): # 종료조건
    	print("원판 1:%s --> %s" % (fr, to)) # 가장 작은 원판을 옮김
    else :
    	hanoi_tower(n-1, fr, to, tmp) # n-1개를 to를 이용해 tmp로
        print("원판 %d: %s --> %s" % (n,fr,to)) # 하나의 원판을 옮김
        hanoi_tower(n-1, tmp, fr, to) # n-1개를 fr를 이용해 to로