当 for() 循环在 if() 语句内时，运行时如何受到影响？

Question

假设我们有这段代码：

doSomething(int n) {
    for(int i = 0; i < n; i++) {
       if (i % 7 == 0) {
           for(int j = 0; j < n; j++) {
              print("*");
           } 
       }
    }
}

什么是 big-O 和 big-omega 运行时（显示 proofs/work）？ if() 语句以及如何证明 big-omega（因为对于 big-O 我们可以忽略条件，因为它是上限）让我大吃一惊。任何帮助深表感谢。谢谢！

Answer 1

让我们开始尝试以更清楚地公开运行时间的方式重写内容。例如，那个内部循环有一个运行时间为 Θ(n)，所以让我们重写代码如下：

for(int i = 0; i < n; i++) {
   if (i % 7 == 0) {
       do Θ(n) work
   }
}

现在，想想这个循环运行时会发生什么。每七次迭代中有一次将触发该内部循环并执行 Θ(n) 工作，而其余七分之六不会并且将在每次迭代中执行 Θ(1) 工作。这意味着完成的总工作是

n ((1 / 7) × Θ(n) + (6 / 7) × Θ(1))

= n(Θ(n) + Θ(1))

= n(Θ(n))

= Θ(n²).

也就是说，这里所做的总功为Θ(n²)。这也是有道理的，因为从本质上讲，if 语句只是将完成的工作减少了 1/7，而 big-O 表示法忽略了常数因子。

您最初为此代码编写了问题：

for(int i = 0; i < n; i++) {
   if (n % 7 == 0) {
       for(int j = 0; j < n; j++) {
          print("*");
       } 
   }
}

这是我原来的回答：

让我们开始尝试以更清楚地公开运行时间的方式重写内容。例如，那个内部循环有一个运行时间为 Θ(n)，所以让我们重写代码如下：

for(int i = 0; i < n; i++) {
   if (n % 7 == 0) {
       do Θ(n) work
   }
}

那么现在让我们想想这里发生了什么。可能发生的事情有两种可能性。首先，n 可能是七的倍数。在这种情况下，if 语句每次都会触发，并且在 n 次外循环迭代中的每一次迭代中，我们都会执行 Θ(n) 运算。因此，我们可以说在最坏情况下所做的总功为 Θ(n²)。我们无法收紧该界限，因为随着 n 变得越来越大，我们将运行ning 保持为越来越多的七的倍数。其次，n 可能不是七的倍数。当这种情况发生时，我们执行 Θ(n) 循环迭代，每个迭代都执行 Θ(1)，因此在最好的情况下，我们将执行 Θ(n) 总工作。

总的来说，这意味着在最坏的情况下我们做 Θ(n²) 的工作，而在最好的情况下我们做 Θ(n) 的工作。因此我们可以说函数的运行time 是 O(n²) 和 Ω(n)，尽管我认为最好和最差的更精确的描述-case 运行时间提供了更多信息。

这里分析的关键是认识到 if 语句要么总是触发要么永远不会触发。这使我们更容易将推理分为两个单独的案例。

请记住，大 O 分析不仅仅是将一堆东西相乘。这是关于考虑如果我们运行程序实际上会做什么，然后考虑逻辑将如何发挥作用。如果您尝试以这种方式进行大 O 分析，您将很少会浪费时间。

当 for() 循环在 if() 语句内时，运行时如何受到影响？

How is runtime affected when for() loop is inside an if() statement?

big-o

conditional

runtime