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

设计和实现四种求解斐波那契数列的不同算法：

1. **递归法**：

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

# 测量运行时间
import time
start_time = time.time()
fibonacci_recursive(30)
end_time = time.time()
print(f"Recursive method took {end_time - start_time} seconds.")

2. **循环迭代法（动态规划）**：

def fibonacci_iterative(n):
    fib_seq = [0, 1] + [0] * (n - 1)
    for i in range(2, n+1):
        fib_seq[i] = fib_seq[i-1] + fib_seq[i-2]
    return fib_seq[n]

# 计时
start_time = time.time()
fibonacci_iterative(30)
end_time = time.time()
print(f"Iterative method took {end_time - start_time} seconds.")

3. **矩阵快速幂法**（利用数学性质优化效率）：

def matrix_multiply(a, b):
    m = [[a[0][0]*b[0][0]+a[0][1]*b[1][0], a[0][0]*b[0][1]+a[0][1]*b[1][1]],
         [a[1][0]*b[0][0]+a[1][1]*b[1][0], a[1][0]*b[0][1]+a[1][1]*b[1][1]]]
    return m

def fibonacci_matrix_power(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    base_matrix = [[1, 1], [1, 0]]
    result = matrix_multiply(base_matrix, base_matrix)
    while n > 1:
        if n % 2 == 1:
            result = matrix_multiply(result, base_matrix)
        base_matrix = matrix_multiply(base_matrix, base_matrix)
        n //= 2
    return result[0][0]

# 计时
start_time = time.time()
fibonacci_matrix_power(30)
end_time = time.time()
print(f"Matrix method took {end_time - start_time} seconds.")

4. **记忆化搜索**（避免重复计算）：

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

# 计时
start_time = time.time()
fibonacci_memoization(30)
end_time = time.time()
print(f"Memoization method took {end_time - start_time} seconds.")

每个方法的时间复杂度和性能都不同，上述示例只给出了基本版本，实际运行时间可能会因Python解释器、环境和硬件等因素而有所变化。