complexity-theory - 空循环的大 O

Question

如果我有这样的循环结构

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++);

O(n ² ) 还是 O(0)？

假设循环内部是一个 if：

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++)
      if(a==b) do();

我想知道最好和最坏的情况，假设do（）是O（1）。

最差： O(n ² ) if 语句总是为真

最佳： O(0) if 语句始终为假

那是对的吗？

score 4 · Accepted Answer

在我们的上下文中，没有 O(0) 这样的东西；如果优化掉，它将是有效的恒定时间（O（1））。

至于是不是这样，没有。正如所写，它仍然是 O(N^number of nested loops)。优化器可能会完全删除代码，但“最坏的情况”是它没有，并且 CPU 正在旋转它的轮子。通过那些循环。

score 3 · Accepted Answer

取 n = 3，对于第一个循环，会发生以下情况：

i = 1
i < 3 => true
  j = 1
  j < 3 => true
  j++
  j < 3 => true
  j++
  j < 3 => false
i++
i < 3 => true
  j = 1
...

无论循环中是否有任何其他代码，所有这些增量和检查仍然需要进行。

所以这将是最好的 + 最坏的情况 O(n ² )。

当然，优化器可能会看到循环中没有任何事情发生并完全删除它。但是说循环的最佳情况是 O(1) 可能会被认为是错误的，即使它在技术上是正确的。

score 1 · Accepted Answer

1

它们是 O(n^2) - 但实际上只有在循环本身的成本很大时才有意义。

于 2013-02-25T21:27:48.933 回答

score 1 · Accepted Answer

for(int i=1; i<n;i++)
    for(int j=1; j<n;j++);

O(n^2)，即使你什么都不做，计数器也会更新。

所以对于第二个问题，最好和最坏的都是 O(n^2)

4 回答 4