#596. NOIP2013TG-7

NOIP2013TG-7

  1. (单选题)斐波那契数列的定义如下:F1=1F2=1Fn=Fn1+Fn2n3F_1=1,F_2=1,F_n=F_{n–1}+F_{n–2}(n≥3)。如果用下面的函数计算斐波那契数列的第 nn 项,则其时间复杂度为( )。
int F(int n)
{
  if(n<=2)
    return 1;
  else
    return F(n-1)+F(n-2);
}

{{ select(1) }}

  • O(1)O(1)
  • O(n)O(n)
  • O(n2)O(n^2)
  • O(Fn)O(F_n)