单选题

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

F(n):

     if n <= 2 return 1

     else return F(n - 1) + F(n - 2)

A

O(n)

B

O(n^2)

C

O(2^n)

D

O(nlogn)

赣ICP备20007335号-2