计算代码的BigO

Question

我在网上看了一篇文章.根据我的理解,下面代码的BigO应该是O(n).由于循环运行n次.但文章中的正确答案显示为O(1).随着解释

该代码声明恰好有4个变量:i,j,k和t.4 =常数= O(1).

怎么样？

根据我的理解,循环运行n次因此O(n)

int fibonacci(int n)
{
   int i = 0, j = 1, k, t;
   for (k = 1; k <= n; ++k)
   {
     t = i + j;
     i = j;
     j = t;
   }
   return j;
}

附上截图

Answer 1

你错误的记忆复杂性的时间复杂性.算法的时间复杂度是O(n).然而,算法的存储器(有时称为空间)的复杂性是O(1),因为分配了4个变量.