如何计算循环中的操作数并给出theta特征 [英] How to count the number of operations in a loop and give a theta characterization

问题描述

我只想确定我是否做对了。我试图计算在Java中最坏情况下执行的操作数。

I just want to make sure if I am doing this correct. I am trying to count the number of operations performed for the worst case scenario in java

int sum = 0;
    for (int i = 0; i < n; i++ )
    sum++;

操作数是2 + 3n还是3 + 3n？

Is the number of operations 2+3n or 3+3n?

我从对int sum = 0和int i = 0的 2计数中得到了答案，而我< n，i ++和sum ++为 3n。还是3，而不是2，因为我必须计算i<

I got the answer from counting int sum = 0 and int i = 0 for the "2" and i < n, i++, and sum++ as the "3n". Or is it a 3 rather than a 2 because I have to count i < n before going through the loop?

但是，无论哪种方式，theta的表征都是Θ（n）吗？

But either way, is the theta characterization going to be Θ(n)?

现在，如果有一个嵌套的for循环，该怎么办：

Now what if there is a nested for loop like this:

int sum = 0;
    for (int i = 0; i < n; i++ )
        for (int a = 0; a < i; a++)
            sum++;

是3 + n *（6a + 2）= 6na + 2n + 3吗？如果我将内部for循环从<更改为Θ（n ^ 2）？

would it be 3+n*(6a+2) = 6na+2n+3? with Θ(n^2)?

我到< i * i，等式仍然保持不变还是会改变？

if i change the inner for loop from a < i to a < i*i, would the equation still hold as above or change?

推荐答案

也许计算每个执行的次数更容易声明每行是否只有一个：

Maybe it's easier to count the number of executions of each statement if there's only one per line:

int sum = 0;     // 1 time
int i = 0;       // 1 time
while (i < n) {  // n+1 times
  sum++;         // n times
  i++;           // n times
}

因此， T（n） = 3 * n + 3 =Θ（n）。

int sum = 0;       // 1 time
int i = 0;         // 1 time
while (i < n) {    // n+1 times
  int a = 0;       // n times
  while (a < i) {  // 1 + 2 + ... + n = n*(n+1)/2 times
    sum++;         // 0 + 1 + ... + n-1 = n*(n-1)/2 times
    a++;           // 0 + 1 + ... + n-1 = n*(n-1)/2 times
  }
  i++;             // n times
}

因此， T（n） = 3 * n + 3 + n *（n-1）+ n *（n + 1）/ 2 =Θ（n ^ 2）。

这篇关于如何计算循环中的操作数并给出theta特征的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！