用 矩阵快速幂 求 斐波那契数列的代码

矩阵快速幂是一种高效的算法，用于计算斐波那契数列。斐波那契数列的定义是每个数字等于前两个数字之和，通常用 F(n) 表示第 n 项。矩阵快速幂利用了 Fibonacci 数列的递推性质可以用矩阵乘法简化求解过程。

下面是用 Python 实现斐波那契数列的矩阵快速幂方法：

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

def power_matrix(matrix, n):
    if n == 1:
        return matrix
    half_n = power_matrix(matrix, n // 2)
    if n % 2 == 0:
        return matrix_multiply(half_n, half_n)
    else:
        return matrix_multiply(matrix_multiply(half_n, half_n), matrix)

def fibonacci(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    # 创建基础矩阵 [[1, 1], [1, 0]]
    base_matrix = [[1, 1], [1, 0]]
    
    # 计算矩阵的n次方
    result = power_matrix(base_matrix, n - 1)
    return result[0][0]

# 测试
print(fibonacci(10))  # 输出斐波那契数列的第10项

在这个代码中，`matrix_multiply` 函数负责矩阵乘法，`power_matrix` 则通过分治策略快速计算矩阵的幂，最后 `fibonacci` 函数结合这两者得到斐波那契数列的值。这种算法的时间复杂度为 O(log n)，比直接递归计算要快得多。