g7-02452. GESP-7级-2025-06-单选-第12题 未做

下面程序的时间复杂度为（ ）。

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}

• A. $O(2^n)$
• B. $O({\varphi }^n)$，$\varphi =\frac{\sqrt{5}-1}{2}$
• C. $O(n^2)$
• D. $O(n)$