다양한 빅오의 피보나치 구현하기

import numpy as np
def Fibonacci_1(number):#O(2^n)
    if(number == 0):
        return 0
    elif(number == 1):
        return 1
    return Fibonacci_1(number-1) + Fibonacci_1(number-2)

def Fibonacci_2(M, number):#O(logn)
     if(number > 1):
         if number % 2 ==0:
             M = Fibonacci_2(M, number/2)
             M = np.dot(M,M)
         elif number % 2 ==1:
             M = Fibonacci_2(M,(number-1)/2)
             M = np.dot(M,M)
             M_1 = np.array([[1,1],[1,0]])             
             M = np.dot(M,M_1)
     return M

def Fibonacci_3(number):
    Fibonacci_T = []
    if number ==0 or number == 1:
        return number
    Fibonacci_T.append(0)
    Fibonacci_T.append(1)
    for i in range(2,number+1):
        Fibonacci_T.append(Fibonacci_T[i-1]+Fibonacci_T[i-2])
    result = Fibonacci_T
    return result

if __name__=='__main__':
    M=np.array([[1,1],[1,0]])
    a = (Fibonacci_2(M,10))
    F2 = a[0][1]
    b = Fibonacci_3(10)
    F3 = b[len(b)-1]
    
    
    print("O(2^n)")
    print(Fibonacci_1(10))
    print("O(log n)")
    print(F2)
    print("O(n)")
    print(F3)