问Theta表示法的运行时

EN

我将为这个古老的渐近格言添加另一个插图

“有疑问的时候，从里到外工作！”

让我们再看一看这些代码：

for(i=n-1; i>=0; i-=2)
   for(j=15; j<100; j+=3)
      sum +=i+j;

让我们从最里面的语句开始，即添加到变量sum中的语句。该语句的运行时独立于此处的任何其他变量，因此它执行Θ(1)工作。因此，让我们像这样重写代码：

for(i=n-1; i>=0; i-=2)
   for(j=15; j<100; j+=3)
      do Theta(1) work

现在，让我们看一下内部的for循环。请注意，无论其他变量的值是多少，此循环始终运行完全相同的次数(大约30ish)。这意味着该循环运行恒定次数并执行恒定数量的工作，因此该循环的最终结果是执行Θ(1)工作。如下所示：

for(i=n-1; i>=0; i-=2)
    do Theta(1) work

所以现在我们把这个留给最后一个循环。这里，我们看到所做的功直接和线性地依赖于n。具体地说，这个循环执行Θ(n)次迭代，并在每次迭代中执行Θ(1)次工作，因此完成的总功是(N)Θ。

请注意，决定运行时的不是for循环的数量，而是这些循环在做什么。计算循环的数量是获得运行时粗略估计的一个好方法，但我上面说明的从内向外工作的方法更精确。