下面程序的时间复杂度为（记忆化只读不写）：
int rec_fib[MAX_N];
int fib(int n) {
if (n <= 1) return n;
if (rec_fib[n] != 0) return rec_fib[n];
return fib(n-1) + fib(n-2); // 未写回 rec_fib[n]
}
- A. O(φⁿ)，φ=(1+√5)/2
- B. O(n)
- C. O(log n)
- D. O(1)
正确答案：A
int rec_fib[MAX_N];
int fib(int n) {
if (n <= 1) return n;
if (rec_fib[n] != 0) return rec_fib[n];
return fib(n-1) + fib(n-2); // 未写回 rec_fib[n]
}
正确答案：A
想系统刷完 GESP C++ 1～8 级真题，并查看每道题的逐题精讲？
进入 GESPPASS 开始练习