斐波那契数列的时间复杂度 [英] Time Complexity of Fibonacci Series

问题描述

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 ++，并且对随机算法的计算时间复杂度颇为痛苦.请帮我！预先感谢.

Hi guys, can anyone know how to compute the time complexity of the function above? I am studying C++ and I am quite suffering about compute time complexity of a random algorithm. Please help me! Thanks in advance.

推荐答案

所示代码依赖于g ++语言扩展，即可变长度数组.

The code shown relies on a g++ language extension, variable length arrays.

即它不是标准的C ++.

I.e. it's not standard C++.

对于两个不同的东西，代码还使用名称 F 误导了一些代码.

The code also misdirects a little by using the name F for two different things.

并且请注意，代码通过索引数组末尾而表现出未定义行为.

And do note that the code exhibits Undefined Behavior by indexing an array beyond its end.

除此之外，它是微不足道的.

Apart from that it's trivial.

在更正代码或将其视为伪代码时，执行 n -1操作的复杂度为O( n ).

When the code is corrected, or is viewed as just pseudo-code, doing n-1 operations has complexity O(n).

这篇关于斐波那契数列的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！