✏️ 纠错
第 188 题 / 共 201 题
12. 下面程序的时间复杂度为（ ）。
int rec_fib(int n) {
if (n <= 2)
return n;
if (rec_fib(n - 1) > 0)
return rec_fib(n - 1) + rec_fib(n - 2);
}
int rec_fib(int n) {
if (n <= 2)
return n;
if (rec_fib(n - 1) > 0)
return rec_fib(n - 1) + rec_fib(n - 2);
}
你真棒！
📝 题目解析
答案：D
知识点：记忆化递归的时间复杂度
解析：程序通过rec_fib数组缓存计算结果，每个fib(n)仅计算一次，总计算次数为O(n)，时间复杂度为线性。
记忆化的核心是计算 fib (n) 后，需将结果存入 rec_fib [n]，否则下次调用 fib (n) 时，rec_fib [n] 仍为 0，会重复递归。当前代码的问题是第 6 行仅 “返回已有值”，但第 7 行递归计算后，没把结果存到 rec_fib [n]。因此，记忆化失效，递归会像普通斐波那契一样重复计算子问题。时间复杂度：普通斐波那契递归的时间复杂度是 O (φⁿ)（φ 是黄金分割比 (√5+1)/2），对应选项 A。
知识点：记忆化递归的时间复杂度
解析：程序通过rec_fib数组缓存计算结果，每个fib(n)仅计算一次，总计算次数为O(n)，时间复杂度为线性。
记忆化的核心是计算 fib (n) 后，需将结果存入 rec_fib [n]，否则下次调用 fib (n) 时，rec_fib [n] 仍为 0，会重复递归。当前代码的问题是第 6 行仅 “返回已有值”，但第 7 行递归计算后，没把结果存到 rec_fib [n]。因此，记忆化失效，递归会像普通斐波那契一样重复计算子问题。时间复杂度：普通斐波那契递归的时间复杂度是 O (φⁿ)（φ 是黄金分割比 (√5+1)/2），对应选项 A。