时间戳

首页 > 解决方案 > 大 O 表示法：内部具有 O(1) 操作的 For 循环

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

问题描述

我正在努力更好地理解大 O 符号，并在课堂上被这个问题难住了。

如果我有一个迭代次数恒定的 for 循环，它在每次迭代时简单地在控制台上打印一些东西：

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

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

这是正确的分析吗？

标签： algorithmbig-oanalysis

解决方案

即使是这样的循环：

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

从技术上讲，它仍然是 O(1)。我不打算在这里讨论大 O 符号的正式定义。但简单来说，大 O 表示法衡量了运行时间相对于输入的增长速度。在这种情况下，无论输入是什么，理论上的运行时间都应该是相同的。（实际上甚至没有输入）。所以你的分析是正确的。

推荐阅读