java - 如何计算循环中的操作次数并给出 theta 表征

Question

我只是想确定我这样做是否正确。我正在尝试计算在 java 中最坏情况下执行的操作数

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

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

我通过计算“2”的 int sum = 0 和 int i = 0 以及“3n”的 i < n、i++ 和 sum++ 得到了答案。或者它是 3 而不是 2，因为我必须在循环之前计算 i < n？

但无论哪种方式，theta 表征都会是 Θ(n) 吗？

现在如果有一个像这样的嵌套 for 循环会怎样:

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 吗？用 Θ(n^2)?

如果我将内部 for 循环从 a < i 更改为 a < i*i，方程式是否仍然像上面那样成立或发生变化？

Answer 1

如果每行只有一个语句，也许更容易计算每个语句的执行次数:

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) .