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++,我对随机算法的计算时间复杂度感到非常痛苦。请帮我!提前致谢。
最佳答案
显示的代码依赖于 g++ 语言扩展,可变长度数组。
即它不是标准的 C++。
该代码还通过使用名称 F
来表示两个不同的事物而造成一些误导。
请注意,代码通过索引超出其末尾的数组表现出未定义的行为。
除此之外它是微不足道的。
当代码被纠正或被视为伪代码时,执行 n-1 操作的复杂度为 O(n)。
关于c++ - 斐波那契数列的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28927851/