下面程序的时间复杂度为( )。
int fib(int n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); }
O(2n)O(2^n)O(2n)
O(ϕn)O(\phi^n)O(ϕn)、其中 ϕ=5+12\phi = \frac{\sqrt{5}+1}{2}ϕ=25+1
O(n)O(n)O(n)
O(1)O(1)O(1)