计并实现四种求解斐波那契数列的算法，并用计时法测量算法的运行时间

斐波那契数列是一个经典的动态规划问题，通常有多种方法可以求解，这里列举四种常见的算法：

1. **递归**：最直观的方法，通过定义F(n) = F(n-1) + F(n-2)，但效率低下，因为存在大量的重复计算。递归的时间复杂度大约是O(2^n)。

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

2. **迭代**：使用循环避免了递归带来的冗余，将计算保存在数组中，时间复杂度降为O(n)。

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

3. **矩阵快速幂**：利用矩阵乘法的性质，可以在O(logn)时间内求出斐波那契数。这种方法适用于大整数计算。

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

def fast_fib(n):
    base_matrix = [[1, 1], [1, 0]]
    if n == 0:
        return 0
    result = matrix_multiply(base_matrix, pow(base_matrix, n - 1))
    return result[0][0]

4. **备忘录化递归**：使用一个缓存存储已计算的结果，避免重复计算，提高效率到O(n)。

cache = {}

def memoized_fib(n):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    result = memoized_fib(n - 1) + memoized_fib(n - 2)
    cache[n] = result
    return result

为了测量这些算法的实际运行时间，你可以使用Python的`timeit`模块：

import timeit

for name, func in {"递归": fib_recursive, "迭代": fib_iterative, 
                   "矩阵快速幂": fast_fib, "备忘录化递归": memoized_fib}:
    print(f"{name}运行时间：{timeit.timeit(lambda: func(30), number=1)}秒")