现在用如下程序来计算斐波那契数列的第 n 项,其时间复杂度为()
斐波那契数列的定义为:F1=1,F2=1,Fn=Fn-1+Fn-2 (n>=3)。
F(n): if n<=2 return 1 else return F(n-1) + F(n-2)
O(n)
O(n^2)
O(2^n)
O(n log n)