大 O 表示法：内部具有 O(1) 操作的 For 循环

Question

我正在努力更好地理解大 O 表示法，但在 class 中遇到了这个问题。

如果我有一个迭代次数恒定的 for 循环，它只是在每次迭代时向控制台打印一些内容：

for(int i=1; i<10; i++)
{
   cout << "Hello!" << endl; 
}

这段代码的大 O 表示法是什么？写入控制台的行需要 1 个时间单位，我会将其乘以它将执行的次数 - 在本例中为 10 - 所以我会得到 O(10)。然而，这只是减少到 O(1)。

这个分析正确吗？

Answer 1

即使是这样的循环：

for (int i = 0; i < 1000000; i++) {
  cout << i << '\n';
}

技术上仍然是 O(1)。我不会在这里详细介绍大 O 表示法的 formal definition。但简单来说，大 O 表示法衡量运行时间相对于输入的增长速度。在这种情况下，无论输入是什么，理论运行时间都应该相同。（事实上什至没有输入）。所以你的分析是正确的。

Big O Notation: For loop with O(1) operation on the inside