g7-02381. GESP-7级-2024-09-单选-第14题 未做

下面 fib 函数的时间复杂度为（ ）。

编者注：官方原题 B 选项此处写作 $\varphi =(\sqrt{5}-1)/2$，但该数小于 $1$，与递归时间复杂度及官方答案 B 矛盾；本题按题意修正为 $\varphi =(\sqrt{5}+1)/2$。

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);
}

• A. $O(n)$
• B. $O({\varphi }^n)$，其中 $\varphi =\frac{\sqrt{5}+1}{2}$
• C. $O(2^n)$
• D. 无法正常结束。