피보나치 수

재귀

def fibonacci(n):
	if n < 2:
		return n

return fibonacci(n-1) + fibonacci(n-2)

구현이 쉽고 간단하다는 장점이 있다.

시간복잡도는 \(O(2^n)\).

다른 알고리즘에 비해 아주 느리다는 단점이 있다.

 

 

반복

def fibonacci(n):
    if n < 2:
        return n
    
    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a+b

    return b

시간복잡도가 \(O(n)\)으로 재귀에 비해 크게 빨라진다.

 

 

반복적 동적 계획법

def fibonacci(n):
    if n < 2:
        return n
    
    cache = [0 for _ in range(n+1)]
    cache[1] = 1

    for i in range(2, n+1):
        cache[i] = cache[i-1] + cache[i-2]

    return cache[n]

cache에 계산한 피보나치 수를 저장해 두는 방식.

 

 

재귀적 동적 계획법

def fibonacci(n):
    cache = [-1 for _ in range(n+1)]

    def iterate(n):
        if n < 2:
            return n
        
        if cache[n] != -1:
            return cache[n]

        cache[n] = iterate(n-1) + iterate(n-2)

        return cache[n]
    
    return iterate(n)

재귀와 동적 계획법을 섞어 놓은 방식이라고 보면 편하다.

cache를 -1로 초기화해두고

이 cache를 통해 재귀함수의 탈출조건을 설정한다.

 

n이 2보다 작으면 n을 그대로 반환하고 재귀함수를 탈출한다.

cache에 이미 n에 대한 피보나치 수가 기록이 되어 있다면 그 피보나치 수를 반환하고 재귀함수를 탈출한다.

이 두 조건을 모두 만족하지 못하면 그 때 n에 해당하는 피보나치 수를 계산한다.

 

 

행렬 곱셈을 활용

def fibonacci(n):
    SIZE = 2
    ZERO = [[1, 0], [0, 1]]
    BASE = [[1, 1], [1, 0]]

    def square_matrix_mul(a, b, size=SIZE):
        new = [[0 for _ in range(size)] for _ in range(size)]
        
        for i in range(size):
            for j in range(size):
                for k in range(size):
                    new[i][j] += a[i][k] * b[k][j]

        return new

    def get_nth(n):
        matrix = ZERO.copy()
        k = 0
        tmp = BASE.copy()

        while 2**k <= n:
            if n & (1 << k) != 0:
                matrix = square_matrix_mul(matrix, tmp)
            k += 1
            tmp = square_matrix_mul(tmp, tmp)
        
        return matrix
    
    return get_nth(n)[1][0]

상당히 복잡한데 아래에 첨부할 링크에서 참고하도록 하자.

시간복잡도는 \(O(log_{2}n)\).

 

 

일반항 사용

def fibonacci(n):
    sqrt_5 = 5 ** (1/2)
    answer = 1 / sqrt_5 * (((1+sqrt_5)/2)**n - ((1-sqrt_5)/2)**n)
    
    return int(answer)

피보나치 수의 일반항을 사용.

수식을 그대로 코드로 옮긴 것.

시간복잡도는 \(O(logn)\)

 

 

위 코드들의 자세한 설명은 모두 이 링크에서 확인할 수 있다.

특히 행렬 곱셈을 활용한 꽤 복잡하니 자세히 보도록 하자.