[재귀호출] 팩토리얼 /피보나치 수열 /순열 시간복잡도

 

 

팩토리얼

def factorial(n):
    if n == 1 || n== 0:
        return 1

    return n * factorial(n - 1)
    
    
n = 3
print("**팩토리얼")
print(factorial(n))

• 시간복잡도 O(N) : N번 계산됨 (3*f(2), 2*f(1), 1,*f(0))
• 공간복잡도 O(N) : 재귀함수 N번 호출됨

 

피보나치수열

def fibo(n):
    if n==1 : return 1
    if n==2 : return 1

    return fibo(n-1)+fibo(n-2)
    
    
print("**피보나치수열")
print(fibo(n))

• 시간복잡도 O(2^N) : 2^N번 연산됨 (f(4)+f(3), f(3)+f(2) f(2)+(1), f(2)+f(1))
• 공간복잡도 O(2^N) : 재귀함수 2^N번 호출됨

 

재귀호출시 memo를 활용하여 시간복잡도를 줄일 수 있다.

def fibo(n):
    memo = [0] * (n + 1)
    memo[1] = 1
    if n >= 2:
        memo[2] = 1

    return __fibo(n, memo)


def __fibo(n, memo):
    if memo[n] > 0:  # 이미 호출된 적이 있어서 memo에 담아두었으면
        return memo[n]
    else:
        res = __fibo(n - 1, memo) + __fibo(n - 2, memo)
        memo[n] = res
        return res


if __name__ == '__main__':
    print(fibo(7))

• 시간복잡도 O(N)

 

순열

def p(x, n,result):
    if x == n : #순열에 있는 숫자의 개수 (x)
        print(result)
        return

    for i in range(1,n+1): # 1부터 n까지 숫자(i) 로 이루어진 순열
        result[x] = i
        p(x+1,n,result)

• 시간복잡도 O(N^X) : N^X
• 공간복잡도 O(X)? :