计算代码的 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)。但是，内存 有时称为 space，算法的复杂度为 O(1)，因为分配了 4 个变量。

Answer 2

形式上，大 O 表示法描述了复杂程度。

要计算大 O 符号：

确定算法复杂度的公式。比方说，两个循环，其中嵌套了另一个循环，然后是另外三个未嵌套的循环：2N² + 3N 删除最高项以外的所有内容：2N² 删除所有常量：N² 换句话说，两个循环和另一个嵌套在里面，然后另外三个没有嵌套的循环是 O(N²)

这当然是假设您在循环中拥有的是简单的指令。例如，如果循环内有 sort()，则必须将循环的复杂性乘以基础 language/library 正在使用的 sort() 实现的复杂性

根据它的数学逻辑，您程序的大 O 表示法是 O(N)，而不是 O(1)。在这种情况下，要么是文章有误，要么是你对文章内容的理解不正确和不完整，这里只放了部分文字。

Answer 3

如果你传递 'n' 一个常量值，它的时间复杂度为 O(1)

// Here c is a constant   


for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

运行固定次数的循环或递归也被视为 O(1)。

如果你传递 'n' 一个变量，它的时间复杂度为 O(n)。

 // Here c is a positive integer constant   


for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

如果循环变量递增/递减恒定量，则循环的时间复杂度被视为 O(n)。

Calculating the BigO for a code