c++ - 斐波那契数列的时间复杂度

Question

long int F(int n){
 long int F[n];
 if (n<2) return n;
 else {
      F[0]=0; F[1]=1;
      for (int i=2; i<n+1; i++)
         F[i]=F[i-1]+F[i-2];
      return F[n]; }
 }

大家好，谁知道如何计算上述函数的时间复杂度？我正在学习 C++，我对随机算法的计算时间复杂度感到非​​常痛苦。请帮我!提前致谢。

Answer 1

显示的代码依赖于 g++ 语言扩展，可变长度数组。

即它不是标准的 C++。

该代码还通过使用名称 F 来表示两个不同的事物而造成一些误导。

请注意，代码通过索引超出其末尾的数组表现出未定义的行为。

除此之外它是微不足道的。

当代码被纠正或被视为伪代码时，执行 n-1 操作的复杂度为 O(n)。