下面 fib 函数的时间复杂度为：
int fib_rcd[MAX_N];
int fib(int n) {
if (n <= 1) return 1;
if (fib_rcd[n] > 0) return fib_rcd[n];
return fib(n-1) + fib(n-2); // 注意：未写回 fib_rcd[n]
}
- A. O(n)
- B. O(φⁿ)，φ=(√5+1)/2（黄金比）
- C. O(2ⁿ)
- D. 无法正常结束。
正确答案：B
int fib_rcd[MAX_N];
int fib(int n) {
if (n <= 1) return 1;
if (fib_rcd[n] > 0) return fib_rcd[n];
return fib(n-1) + fib(n-2); // 注意：未写回 fib_rcd[n]
}
正确答案：B
想系统刷完 GESP C++ 1～8 级真题，并查看每道题的逐题精讲？
进入 GESPPASS 开始练习