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

Question

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

\n\n

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

\n\n

运算次数是2+3n还是3+3n？

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

是 3+n*(6a+2) = 6na+2n+3 吗？与 \xce\x98(n^2)？

\n\n

如果我将内部 for 循环从 a < i 更改为 a < i*i，方程是否仍然如上保持或改变？

\n

Answer 1

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

\n\n

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

\n\n

因此，T(n) = 3*n+3 = \xce\x98(n)。

\n\n

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

\n\n

因此，T(n) = 3*n+3 + n*(n-1) + n*(n+1)/2 = \xce\x98(n^2)。

\n