下面 fibonacci 函数的时间复杂度为( )。
fibonacci
int fibonacci(int n) { if (n <= 1) return n; else return fibonacci(n - 1) + fibonacci(n - 2); }
O(1)O(1)O(1)
O(ϕn),ϕ=5−12O(\phi^n), \phi = \frac{\sqrt{5}-1}{2}O(ϕn),ϕ=25−1
O(n)O(n)O(n)
O(nlogn)O(n \log n)O(nlogn)