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

{{ select(1) }}

• $O(n)$
• $O(\phi^n),\phi=\dfrac{\sqrt{5}-1}{2}$
• $O(2^n)$
• 无法正常结束。