java 如何计算循环中的操作次数并给出θ表征
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3817491/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to count the number of operations in a loop and give a theta characterization
提问by Dan
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
我只是想确定我这样做是否正确。我正在尝试计算在 Java 中为最坏情况执行的操作数
int sum = 0;
for (int i = 0; i < n; i++ )
sum++;
Is the number of operations 2+3n or 3+3n?
操作次数是2+3n还是3+3n？
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?
我通过将 int sum = 0 和 int i = 0 计算为“2”和 i < n、i++ 和 sum++ 作为“3n”得到了答案。或者它是 3 而不是 2 因为我必须在循环之前计算 i < n ？
But either way, is the theta characterization going to be Θ(n)?
但无论哪种方式，theta 表征将是 Θ(n) 吗？
Now what if there is a nested for loop like this:
现在，如果有这样一个嵌套的 for 循环怎么办：
int sum = 0;
for (int i = 0; i < n; i++ )
for (int a = 0; a < i; a++)
sum++;
would it be 3+n*(6a+2) = 6na+2n+3? with Θ(n^2)?
会是 3+n*(6a+2) = 6na+2n+3 吗？与 Θ(n^2)？
if i change the inner for loop from a < i to a < i*i, would the equation still hold as above or change?
如果我将内部 for 循环从 a < i 更改为 a < i*i，方程是否仍保持如上或改变？
回答by Sheldon L. Cooper
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
}
Hence, T(n) = 3*n+3 = Θ(n).
因此，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
}
Hence, T(n) = 3*n+3 + n*(n-1) + n*(n+1)/2 = Θ(n^2).
因此，T(n) = 3*n+3 + n*(n-1) + n*(n+1)/2 = Θ(n^2)。
回答by Albert
Yes, exactly. Look herefor a mathematical definition.
对，就是这样。看看这里的数学定义。
It doesn't matter if you use 2+3n or 3+3n. You have lim_n->infty ( (3+3n)/n ) = 3 (both lim sup and lim inf are the same here). Because of that limites (which is greater 0 and not infinity), you know that is Big Theta n.
使用 2+3n 还是 3+3n 都没有关系。你有 lim_n->infty ( (3+3n)/n ) = 3 （这里的 lim sup 和 lim inf 都是一样的）。由于这个限制（大于 0 而不是无穷大），你知道那是大 Theta n。
In your second example, you cannot use the inner-loop variables (a or i). The amount of sum++ operations:
在您的第二个示例中，您不能使用内部循环变量（a 或 i）。sum++运算量：
- When i == 0: zero
sum++s are executed. - When i == 1: exactly one
sum++get's executed (when a==0). - When i == 2: 2
sum++s (a==0 and a==1) - When i == 3: 3
sum++s (a==0, a==1 and a==2) - ...
- When i == n-1: n-1
sum++s (a==0, a==1, ... and finally a==n-1)
- 当 i == 0 时：
sum++执行零。 - 当 i == 1 时：恰好一个
sum++get 被执行（当 a==0 时）。 - 当 i == 2: 2
sum++s (a==0 and a==1) - 当 i == 3: 3
sum++s (a==0, a==1 and a==2) - ...
- 当 i == n-1: n-1
sum++s (a==0, a==1, ... 最后是 a==n-1)
That are all sum++s in your code. So let's sum them together:
这就是sum++你的代码中的所有s。所以让我们总结一下：
0 + 1 + 2 + ... + n - 1
That is the same as (n-1)(n-2)/2.
这与 (n-1)(n-2)/2 相同。
I.e. we have Θ(n^2 + n). The same thing for a++ and a < i (well, one more to be exact but that doesn't matter). The amount of i++ ops is just n. So you end up with Θ(n^2).
即我们有 Θ(n^2 + n)。对于 a++ 和 a < i 来说是一样的（嗯，准确地说，还有一个，但这并不重要）。i++ 操作的数量仅为 n。所以你最终得到了 Θ(n^2)。
回答by Andrew Cooper
It'll be 3+3n, because the comparison runs for each value of ifrom 0 to ninclusive. I'd says that's O(n).
它将是 3+3n，因为比较会针对i从 0 到n包含在内的每个值运行。我会说这是 O(n)。
回答by poke
I would it count as 3+3n, because when n = 0then you execute the following 3 commands:
我会把它算作3+3n，因为当n = 0你执行以下 3 个命令时：
int sum = 0;
int i = 0;
i < n
Now when n != 0then you execute the declarations once (2) and for each execution of the loop each command once (3n) and the final comparison (which fails; 1). That makes 3+3n.
现在，当n != 0您执行一次声明 ( 2) 并且每次执行循环时，每个命令执行一次 ( 3n) 和最终比较（失败；1）。这使得3+3n.
And yes, that would be Θ(n) (and O(n) and o(n)).
是的，那将是 Θ(n)（以及 O(n) 和 o(n)）。
