a_{1} = a_{2} = 1 \\ 
a_{n+2} = a_{n+1} + a_{n}\;\;\;\;\;(n >= 1) 

#From the Fibonacci sequence formula, it is as follows.
#At this time, the fibonacci function is called many times to get the numerical value of n.
#Therefore, the algorithm is simple, but the processing is slow.
import time 


def fibonacci_simple(n):
    if (n == 1) or (n == 2):
        return 1
    return fibonacci_simple(n - 2) + fibonacci_simple(n - 1)


start = time.time()
print(fibonacci_simple(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

6765
elapsed_time:0.002089977264404297[sec]

#Speed up processing by memoizing.
#The value of the conditional array is put in the associative array called memo.
#memo If there is always, it ends. If not, calculate and insert into memo
#The same calculation can be eliminated.
import time


memo = {1: 1, 2: 1}
def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1)
    return memo[n]


start = time.time()
print(fibonacci_memo(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

6765
elapsed_time:0.0002808570861816406[sec]

#Use a loop to find it.
import time


def fibonacci_loop(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i -2] + fib[i - 1])
        
    return fib[n - 1]


start = time.time()
print(fibonacci_loop(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

6765
elapsed_time:0.00026702880859375[sec]

Recommended Posts