java - 计算代码的 BigO

Question

我在网上阅读了一篇文章。根据我的理解，以下代码的 BigO 应该是 O(n)。因为循环运行了 n 次。但是文章中的正确答案显示为 O(1)。带说明

The code declares exactly 4 variables: i, j, k and t. 4 = constant = 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 个变量。