算法的时空复杂度 - 大O符号

Question

我试图分析一个简单算法的Big- O -otation,并且我已经用了一段时间了.所以我根据以下代码的规则进行分析并试图弄清楚这是否正确:

public int Add()
{
  int total = 0; //Step 1

  foreach(var item in list) //Step 2
  {
    if(item.value == 1) //Step 3
    {
      total += 1; //Step 4
    }
  }
  return total;
}

1. 如果指定变量或集合,则在这种情况下,根据Big O的规则确定复杂度为O(1).所以第一阶段将是O(1) - 这意味着无论输入大小是什么,程序将执行相同的时间和内存空间.

2. 第二步是foreach循环.循环中有一点很清楚.根据输入,循环迭代或运行.作为示例,对于输入10,循环迭代10次并且持续20次,20次.完全取决于输入.根据Big O的规则,复杂性将是O(n) - n是输入的数量.因此,在上面的代码中,循环根据列表中的项目数进行迭代.

3. 在此步骤中,我们定义一个确定条件检查的变量(参见编码中的步骤3).在这种情况下,根据Big O规则,复杂度为O(1).

4. 以相同的方式,在步骤4中,也没有变化(参见编码中的步骤4).如果条件检查为真,则total变量将值递增1.因此我们写 - 复杂度O(1).

因此,如果上述计算是完美的,那么最终的复杂性如下:

O(1) + O(n) + O(1) + O(1) or (O(1) + O(n) * O(1) + O(1))

我不确定这是否正确.但是我猜想,如果这不是一个完美的话,我会期待一些澄清.谢谢.

Answer 1

你的分析并不完全正确。

1. 第 1 步确实需要 O(1) 次操作
2. 第 2 步确实需要 O(n) 次操作
3. 步骤 3 需要 O(1) 次操作，但执行了 n 次，因此它对复杂性的整体贡献是 O(1*n)=O(n)
4. 步骤 4 需要 O(1) 次操作，但最多执行 n 次，因此它对复杂性的整体贡献也是 O(1*n)=O(n)

整个复杂度为 O(1)+O(n)+O(n)+O(n) = O(n)。