I show you ways to implement fibonacci algorithms

fibonacci_collections.py

# 피보나치를 해결하는 5가지 방법을 소개합니다.
# 모든 입력은 0 이상의 정수라고 가정합니다.



#1. 가장 일반적인 식, 복잡도는 O(2 ** n)
def fibonacci(n):
  return fibonacci(n-1) + fibonacci(n-2) if n >= 2 else n





#2. 파이썬 공식문서에 소개되고 있는 쉬운 식. 복잡도는 O(n)
def fibonacci(n):
  a, b = 1, 0
  for _ in range(n):
    a, b = a + b, a
  return b





#3. memoization. 캐시를 이용해 #1의 비효율을 해결하라. 복잡도는 O(n)
def fibonacci(n, _cache={0: 0, 1: 1}):
  if n in _cache:
    return _cache[n]
  else:
    v = fibonacci(n-1) + fibonacci(n-2)
    _cache[n] = v
    return v
  
  
#4. 행렬 곱셈. 복잡도는 O(log2)
def fibonacci_matrix(n):
    BASE = [[1, 1], [1, 0]]
    ZERO = [[1, 0], [0, 1]]
    L = 2
    k = 0
    while 2 ** k <= n:
        k += 1
    k -= 1
    rest = n - 2 ** k

    if n == 0:
        return ZERO
    elif n == 1:
        return BASE


    def two_by_two(a, b):
        L = 2
        tmp = [[0, 0], [0, 0]]
        for i in range(L):
            for j in range(L):
                for k in range(L):
                    tmp[i][j] += a[i][k] * b[k][j]
        return tmp


    def _k_th_matrix(k):
        base = BASE.copy()
        for _ in range(k):
            base = two_by_two(base, base)

        return base

    matrix = _k_th_matrix(k)
    print(matrix)

    if rest == 0:
        return matrix
    else:
        return two_by_two(matrix, fibonacci_matrix(rest))