使用 O(log n) 的时间复杂度C语言实现计算斐波那契数列第n项值，并说明数学原理

以下是使用 O(log n) 时间复杂度的 C 代码实现斐波那契数列第n项的计算：

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int fib[2][2] = {{1, 1}, {1, 0}};
    int ans[2][2] = {{1, 0}, {0, 1}};
    int temp[2][2];

    while (n > 0) {
        if (n % 2 == 1) {
            temp[0][0] = ans[0][0] * fib[0][0] + ans[0][1] * fib[1][0];
            temp[0][1] = ans[0][0] * fib[0][1] + ans[0][1] * fib[1][1];
            temp[1][0] = ans[1][0] * fib[0][0] + ans[1][1] * fib[1][0];
            temp[1][1] = ans[1][0] * fib[0][1] + ans[1][1] * fib[1][1];

            ans[0][0] = temp[0][0];
            ans[0][1] = temp[0][1];
            ans[1][0] = temp[1][0];
            ans[1][1] = temp[1][1];
        }

        temp[0][0] = fib[0][0] * fib[0][0] + fib[0][1] * fib[1][0];
        temp[0][1] = fib[0][0] * fib[0][1] + fib[0][1] * fib[1][1];
        temp[1][0] = fib[1][0] * fib[0][0] + fib[1][1] * fib[1][0];
        temp[1][1] = fib[1][0] * fib[0][1] + fib[1][1] * fib[1][1];

        fib[0][0] = temp[0][0];
        fib[0][1] = temp[0][1];
        fib[1][0] = temp[1][0];
        fib[1][1] = temp[1][1];

        n /= 2;
    }

    return ans[0][1];
}

int main() {
    int n = 10;
    printf("斐波那契数列第%d项的值为：%d\n", n, fibonacci(n));
    return 0;
}

这个算法的时间复杂度为 O(log n)，因为它将斐波那契矩阵的幂以指数级别缩小。使用这种方法，我们可以通过 n 的对数级别来计算斐波那契数列的第 n 项。该算法的基本原理是利用斐波那契矩阵的幂和二进制展开来计算斐波那契数列的第 n 项。

斐波那契数列是指：第 0 项为 0，第 1 项为 1，从第 2 项开始，每一项