c++ - 计算嵌套循环的大 O

Question

我在为以下代码计算 Big O 时遇到问题。我从来都不是最聪明的饼干。有人可以解释一下吗。由于嵌套循环，我的猜测是 O(N^2)，但我知道还有更多。

static inline int f1 (int a, int b)
{
 for (int c = 0; c < b; c++)
 {
   a -= n;
 }
 return a;
}

int f2 (int n) 
{
  int r = n * n * n;
  for (double i = n; i >= 0; i -= 2)
  {
     r = f1(r, i);
  }
  return r;
}

Answer 1

首先，请注意 f1 的运行时间完全取决于第二个参数，它控制循环迭代的次数。因此，它的运行时间在第二个参数中是线性的。

接下来，请注意 f2 中的循环运行 n/2 次，其中 i 取值 0、2、4、6、...、n。由于 i 是 f1 的第二个参数，因此运行时间由下式给出

0 + 2+ 4+ ... + n

= 2(0 + 1+ 2+ .. + n)

= 2Θ(n^2)

= Θ(n^2)

所以运行时间是 Θ(n^2)。请注意，几乎所有其他内容都是为了误导您的分心。仅关注控制迭代和循环的变量会揭示您需要关注的实际逻辑。

希望这可以帮助！

Answer 2

1. 请尽量避免将 float/double 作为 for 循环计数器，因为它们不精确。使用 size_t 或任何其他 int 类型。此外，据我可以从您的代码中告诉您，无论如何您都将 i 从 double 转换为 int ，因此那里不需要那个 double 。

2. 你的循环可以这样写：

   int r = n * n * n;
   for (double i = n; i >= 0; i -= 2)
   {
     for (int c = 0; c < i; c++)
     {
       r -= n;
     }
   }
   

外循环：O(n/2) - 每步“跳跃”2 个单位 => 操作数为 n/2

内循环：O(n/2) - 从技术上讲，它迭代到 i，但是因为 i 具有 n/2 的最大值并且内循环上升 1 乘 1 => 复杂度是相同的 n/2

整体复杂度：O((n/2)^2)

更新

正如其他人所建议的那样，是的，您可以折叠常量部分（在本例中为“/ 2”），但在我看来，它更清楚，就像我最初发布的那样。希望这也有帮助。

Answer 3

从数学上讲，你可以像下面这样正式地进行：

其中op是在 中执行的恒定时间操作的数量f1()。我可以添加op'或这样的 for f2()，但这似乎没有必要。

要计算操作的数量，比如 T(10)，只需让op = 1.