当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 Runtimes是什么（显示的证明/工作）？我的脑海被if（）语句以及如何证明大欧洲的震惊（因为对于Big-O，我们可以忽略条件，因为它是上限）。任何帮助深表感谢。谢谢！

Answer 1

让我们首先尝试以更清楚地揭示运行时的方式重写内容。例如，该内部循环的运行时间为＆theta;（n），所以让我们重写这样的代码：

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

现在，考虑一下此循环运行时会发生什么。每七个迭代中的一个中有一个会触发那个内部循环和theta;（n）工作，其余的六十分之一将不会并且会做到;（1）（1）根据迭代的工作。这意味着完成的总工作是

n（（1/7）＆times;＆theta;（n） （6/7）＆times;＆theta;（1））

= n（＆theta;（n） ＆theta;（1））

= n（＆theta;（n））

=＆theta;（n ² ）。

换句话说，这里完成的总工作是＆theta;（n ² ）。而且这也很有意义，因为从本质上讲，如果语句仅将所做的工作减少了1/7，而Big-O表示法则忽略了不断的因素。

---

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

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

这是我的原始答案：

让我们开始尝试以更清楚地揭示运行时的方式重写内容。例如，该内部循环的运行时间为＆theta;（n），所以让我们重写这样的代码：

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

所以现在让我们考虑一下这里发生的事情。可能发生的事情有两种可能性。首先，可能是n是七个的倍数。在这种情况下，if语句每次都会触发我们所做的n外循环迭代中的每一个。（n）工作。因此，我们可以说在最坏情况下完成的总工作将为＆theta;（n ² ）。我们不能拧紧这种绑定，因为随着n的变化，我们不断遇到越来越多的七个倍数。其次，可能是n不是七个中的倍数。发生这种情况时，我们会做＆theta;（n）循环迭代，所有这些都可以＆theta;（1）每个工作，所以在最好的情况下，我们会做的＆theta;（n）总工作。

总的来说，这意味着在最坏的情况下，我们确实做到了（n ² ）工作，在最好的情况下，我们做的是（n）工作。因此，我们可以说功能的运行时间是O（N ² ）和＆omega;（n），尽管我认为对最好和最差的运行时间更精确的描述是更多内容丰富。

这里的分析的关键是指出，如果说明要么总是要开火，要么永远不会开火。这使我们更容易将推理分为两个单独的情况。

请记住，Big-O分析不仅仅是将一堆事物倍增。这是关于如果我们要运行该程序将实际做什么，然后考虑逻辑将如何发挥作用。如果您尝试以这种方式进行Big-O分析，您将很少浪费时间。