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

斐波那契数列是一个经典的数学序列，其中每个数字都是前两个数字之和。下面介绍四种常见的求解斐波那契数列的算法：

1. **递归**：最直观也是最容易理解的方法，但效率较低。由于递归会涉及大量重复计算。

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

运行时间：O(2^n)

2. **循环迭代**：通过循环避免了递归带来的冗余计算，提高效率。

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

运行时间：O(n)

3. **动态规划**：使用数组存储中间结果，避免重复计算。

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

运行时间：O(n)

4. **矩阵快速幂**：利用矩阵乘法的性质加速计算，适用于大数情况。

   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 fib_matrix(n):
       phi = [[1, 1], [1, 0]]
       result = matrix_power(phi, n - 1)
       return result[0][0]

运行时间：O(log n) (对于大数n)

为了测量每个算法的运行时间，你可以使用Python的`timeit`模块或第三方库如`time`和`cProfile`。

import timeit

for func_name in ['fib_recursive', 'fib_iterative', 'fib_dynamic', 'fib_matrix']:
    print(f"{func_name} 的运行时间: {timeit.timeit(setup=f"from __main__ import {func_name}", number=1)}秒")