1:

# 计算Fibonacci数:
# Naive版本,时间效率O(1.618^n)
# 记忆化版本(增加line8、10、13),时间效率O(n)
# 注意:当n超过1000,可能超过系统允许的最大递归深度

from time import process_time

# memo = {}
def fib(n):
    # if n in memo: return memo[n]
    if n < 2: f = n
    else: f = fib(n-2) + fib(n-1)
    # memo[n] = f
    return f

n = int(input('n = '))
start = process_time()
print(fib(n))
elapsed = (process_time() - start)
print("用时(秒):",elapsed)

2:

# 计算Fibonacci数:
# 迭代版本,时间效率O(n),空间效率O(n)
# 注意:当n超过1000000,可能出现Memory Error

from time import process_time

memo = {}
def fib(n):
    for i in range(n+1):
        if i < 2: f = i
        else: f = memo[i-1]+memo[i-2]
        memo[i] = f
    return memo[n]

n = int(input('n = '))
start = process_time()
print(fib(n))
elapsed = (process_time() - start)
print("用时(秒):",elapsed)

3:

# 计算Fibonacci数:
# 空间效率优化为O(2),时间效率O(n)

from time import process_time

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

n = int(input('n = '))
start = process_time()
print(fib(n))
elapsed = (process_time() - start)
print("用时(秒):",elapsed)

4:

# 计算Fibonacci数:
# 利用矩阵幂次求解,由于使用分治方法,时间效率O(log(n))

from time import process_time

def fib(n):

    F = [[1, 1],
         [1, 0]]
    if (n == 0):
        return 0
    power(F, n - 1)

    return F[0][0]

def multiply(F, M):

    x = (F[0][0] * M[0][0] +
         F[0][1] * M[1][0])
    y = (F[0][0] * M[0][1] +
         F[0][1] * M[1][1])
    z = (F[1][0] * M[0][0] +
         F[1][1] * M[1][0])
    w = (F[1][0] * M[0][1] +
         F[1][1] * M[1][1])

    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(F, n):

    if( n == 0 or n == 1):
        return;
    M = [[1, 1],
         [1, 0]];

    power(F, n // 2)
    multiply(F, F)

    if (n % 2 != 0):
        multiply(F, M)

n = int(input('n = '))
start = process_time()
print(fib(n))
elapsed = (process_time() - start)
print("用时(秒):",elapsed)
12-14 11:31
查看更多