查找语句运行的次数 [英] Finding the number of times a statement runs

问题描述

找出foo语句在以下程序中运行的次数.我们假设n是偶数.

I am told to figure out the number of times the statement foo runs in the following program. We are assuming that n is an even number.

j = 1;
while( j <= n/2 ) 
{
  i = 1;
  while( i <= j ) 
  {
    foo;
    i++;
  }
  j++;
}

我认为最好的方法是从内循环开始，然后向外发展.我们知道i = 1，并且在内循环内部有i <= j.这意味着此内部循环运行j次. (这是我开始感到困惑的地方)在外循环中，我们看到了j <= n/2语句，这意味着该外循环运行了n/2次，对吗?计算foo运行的次数，应该是j次n/2，不是吗?那么foo运行j * (n / 2)次?这是正确的吗?

I figured the best way to go about this would be start from the inner loop and work my way outward. We know that i = 1 and inside the inner loop we have i <= j. That means this inner loop runs j times. (This is where I start to get confused) In the outer loop, we see the statement j <= n/2 so that means this outer loop runs n/2 times, right? to count the number of times foo runs, it would be j times n/2, wouldn't it? So foo runs j * (n / 2) times? Is this correct?

推荐答案

我们可以看到 j 递增1直到n/2，而对于内部循环的每次迭代， j 次，将 i 递增1到1- j .

As we can see j increments by 1 till n/2, while for every iteration inner while loop runs j times, increment i by 1 to 1-j.

foo运行1次时，每次内部迭代.

And for every iteration of inner while foo runs 1 time.

对于第一次迭代，第一次迭代 j = 1，foo运行1次..

For first iteration first iteration j = 1, foo runs 1 time..

对于第二个 j = 2，foo运行2次... 对于第n/2次迭代 j = n/2，foo运行n/2次..

For second j=2, foo runs 2 times... For n/2nd iteration j = n/2, foo runs n/2 times..

所以foo总共运行

1 + 2 + 3 + ... + n/2 次
即n/2 *(((n/2 +1))/2 = n/4 *(n/2 +1)=&θ;(n ² )

这篇关于查找语句运行的次数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！