设计四种求斐波那契数列的算法并测量运算时间

设计四种求斐波那契数列的算法：

1. **递归法**：最直观的一种方式，通过定义F(n) = F(n-1) + F(n-2)，但递归会有大量的重复计算，效率较低。适用于教学演示，不适合大量计算。

def fibonacci_recursive(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

2. **循环迭代法**：利用两个变量保存前两个数，每次更新这两个变量直到达到第n项。

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

3. **矩阵快速幂法**：这是一种更高效的数学方法，通过矩阵乘法避开递归带来的重复计算，时间复杂度接近O(log n)。

def matrix_power(matrix, n):
    if n <= 1:
        return matrix
    half = matrix_power(matrix, n // 2)
    if n % 2 == 0:
        return half * half
    else:
        return half * half * matrix

def fibonacci_matrix(n):
    if n <= 0:
        return 0
    fib_matrix = [[1, 1], [1, 0]]
    result = matrix_power(fib_matrix, n - 1)
    return result[0][0]

4. **备忘录动态规划**：将已计算过的值存储在一个列表中，避免重复计算。

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

为了测量这些算法的运算时间，你可以使用Python内置的`timeit`模块或其他性能测试工具，对每个函数分别计算多次求解特定斐波那契数值的时间，并比较它们的速度。例如：

import timeit

for func_name in ['fibonacci_recursive', 'fibonacci_iterative', 'fibonacci_matrix', 'fibonacci_memo']:
    print(f"Function {func_name} runtime for n={10}: {timeit.timeit(func_name(10), number=100)} seconds")