面试题：C语言优化递归算法的时空复杂度

Question

给定一个用C语言编写的递归算法来计算斐波那契数列（例如常规的递归实现`int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }`），该算法时间复杂度较高且空间消耗大。请优化此算法，使其在时间复杂度和空间复杂度上都有显著提升。详细说明优化思路，对比原算法和优化后算法的时空复杂度，并解释在实际应用场景中这种优化的意义。

Answer 1

优化思路

1. 动态规划（自底向上）：
   • 原递归算法存在大量重复计算，例如计算fibonacci(n)时，fibonacci(n - 1)和fibonacci(n - 2)会被多次计算。
   • 动态规划方法通过保存已经计算过的子问题结果来避免重复计算。可以使用一个数组来存储斐波那契数列的中间结果。
   • 从fib(0)和fib(1)开始，逐步计算到fib(n)，这样每个子问题只计算一次。
2. 优化空间复杂度：
   • 观察斐波那契数列的计算过程，发现每次计算只需要前两个数，因此不需要保存整个数列。可以只用两个变量来保存前两个数，从而将空间复杂度从$O(n)$优化到$O(1)$。

优化后代码（C语言）

#include <stdio.h>

int optimizedFibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, result;
    for (int i = 2; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
}

时空复杂度对比

1. 原递归算法：
   • 时间复杂度：$O(2^n)$。因为每次递归调用会产生两个新的递归调用，形成一个二叉树结构，树的深度为$n$，节点数近似为$2^n$。
   • 空间复杂度：$O(n)$。递归调用栈的深度最大为$n$，所以空间复杂度为$O(n)$。
2. 优化后算法：
   • 时间复杂度：$O(n)$。通过循环从$2$到$n$依次计算，每个数只计算一次，所以时间复杂度为$O(n)$。
   • 空间复杂度：$O(1)$。只使用了三个变量（a，b，result），与$n$的大小无关，所以空间复杂度为$O(1)$。

实际应用场景中优化的意义

1. 性能提升：在计算较大的斐波那契数时，原递归算法会花费大量时间，甚至导致程序崩溃（栈溢出）。优化后的算法能够快速得到结果，提高程序的响应速度。
2. 资源节省：在资源受限的环境（如嵌入式系统）中，优化后的算法占用更少的内存，使得程序能够在有限的资源下运行。
3. 可扩展性：对于需要频繁计算斐波那契数列或者类似递归结构问题的应用，优化后的算法能够更好地支持大规模数据的处理，保证系统的稳定性和高效性。