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("*"); 
      } 
     } 
    } 
} 

是什么（用样张/工作）的大O和大欧米伽运行时间？ 我的思想正在被if（）语句和如何证明big-omega所吹捧（因为对于big-o我们可以忽略这个条件，因为它是一个上限）。 任何帮助，非常感谢。谢谢！

Answer 1

我们首先尝试以更清楚地暴露运行时的方式重写事物。例如，内环有Θ（N）运行时，让我们改写这样的代码：

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

现在，想想当这个循环运行时会发生什么。每7次迭代中就有一次会触发内部循环，并执行Θ（n）工作，剩余的六分之七不会执行每次迭代的Θ（1）工作。这意味着，所做的总功是

N（（1/7）× Θ（N）+（6/7）× Θ（1））

= N（Θ（N）+ Θ（1））

= N（Θ（n））的

= Θ（N ）。

换句话说，这里所做的总功是Θ（N ）。而且这也是有道理的，因为基本上，如果陈述只是将所做的工作减少了1/7倍，而大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可能是7的倍数。在这种情况下，if语句每次触发，并且在n个外循环迭代中的每一个上，我们都会执行Θ（n）。因此，我们可以说在最坏的情况下完成的总工作将是Θ（n ）。我们不能收紧这个界限，因为随着n变得越来越大，我们继续跑到越来越多的七倍。其次，n可能不是7的倍数。当发生这种情况时，我们做了Θ（n）循环迭代，它们都做了Θ（1），因此在最好的情况下，我们会做Θ（n）全部工作。

总体而言，这意味着，在最坏的情况下，我们做Θ（N ）工作，并在最好的情况下，我们做Θ（n）的工作。因此，我们可以说该函数的运行时间是O（n ）和Ω（n），但我认为对最佳和最坏情况运行时的更精确的描述会提供更多的信息。

这里分析的关键是意识到，如果陈述要么总是要开火或者永远不会开火。这使我们更容易将推理分为两个独立的案例。

请记住，大O分析不仅仅是将一堆事物放在一起。这是关于如果我们要运行它，然后考虑逻辑将如何发挥，那么程序实际上会做什么。如果你尝试用这种方式来处理大O分析，你很少会浪费你的时间。