确定方法的运行时间

Question

Static void doIt (int n ) {
    int i;      // 1 operations
    int j; ← (2 x n)    // 1 operations
    while loop (j > 0) {    // n operations 
        I; ← n          // (n+1) operations
            while loop ( i>= 1) {   // (n*n) operations
                I;   ← i/2          // sqrt (n) operations
            }
            j; ← j -1           // (n+1) operations
     }
}

Static int myMethod (int n) {
    sum;  ←     // 1 operations
    for i ← 1 to n {    // (n operations)
        sum = sum + doIt(i);    // (n+1) operations
    }
    return 1;   // a 
}

这是我对此伪代码的解决方案，但不确定它是否正确

T(n) = 1 + 1 + n + (n+1) + (n*n) + sqrt(n) + 1 + n + (n+1) + a = n^2 + 5n + 5 + sqrt(n)  
big-o complexity = O(n^2)

Answer 1

我会做一些假设。例如，我假设

int j; ← (2 x n)

用

j

初始化

2*n

。我没想到会有这个分号，但否则我无法继续。

考虑到这一点，您的解决方案是错误的。

while loop (j > 0) {    // n operations

由于

j

是用

2n

初始化的，并且一次减少一个单位，那么这将执行

2n + 1

步骤，而不是

n

。递减将执行

2n

步骤，验证将

+1

带入方程。

然后是内循环：

while loop ( i>= 1) {   // (n*n) operations
    I;   ← i/2          // sqrt (n) operations
}

假设

i

和

I

是同一个变量，那么赋值

I <- I/2

将不会执行

sqrt(n)

，而是在外循环的每次迭代中最多执行

log2(n)

步骤。因此，

while

循环将运行外部循环与该值的乘积，即以

2n × log2(n)

为上限的值。

如果你修复并总结所有内容，你会发现

doIt

是 O(n logn)。确切的值涉及

log2(n)

的上限和一些常数。

另一个函数，

myMethod

，有一个 for 循环：

sum = sum + doIt(i);    // (n+1) operations

这条线将运行

n

次，而不是

n + 1

。如果你不需要精确的函数，也就是说，如果你只是寻找 O 表示法的上限，那么这就是 O(n)。

由于您调用 O(n logn) 算法 O(n) 次，因此整个算法的复杂度为 O(n² logn)。

Answer 2

好吧，让我们分解一下这段代码。我们有几个函数在做他们的事情。首先，有一个 doIt 的事情：

void doIt(int n) {
int i;          // 1 op
int j = 2 * n;   // 1 op
while (j > 0) {  // n loops
    i = n;       // (n+1) ops
    while (i >= 1) {  // n loops
        i = i / 2;    // sqrt(n) ops
    }
    j = j - 1;    // (n+1) ops
  }
}

现在，进入主要部分，myMethod：

int myMethod(int n) {
    int sum = 0;      // 1 op
    for (int i = 1; i <= n; i++) {  // n loops
        sum = sum + doIt(i);        // (n+1) ops
    }
    return 1;          // 1 op
}

现在，让我们将所有这些操作相加并简化方程。我们最终得到：

T(n) = n^2 + 3n + 3 + n * sqrt(n)

现在，从长远来看，这里的大老板术语是

n^2

。所以，用程序员的行话来说，我们称之为

O(n^2)