0

我在我的算法书上找到了这段代码，但我无法理解这个例子。

这是代码：

for(i=1;i<n-1;i++){
   for(j=n;j>i+1;j--){
      if(a[j-1]>a[j]){
         t=a[j-1];
         a[j-1]=a[j];
         a[j]=t;
    }
  }
}

现在根据书本计算的每个部分的复杂性是这样的这个

以及整个代码的大O是这样计算的这个

但我无法理解。你能向我解释一下这段代码的复杂性吗？尤其是计算复杂性的部分，O(n/2)因为术语j>i+1

4

2 回答 2

0

外循环执行 i=1 到 n-2 即 n-2 次。内部循环执行 (n-3), (n-4),......, n-(n-1) 总共 n-3+n-4+n-5+...+ 2+1次。当 i=1 内循环执行 (n-3) 次时，当 i=(n-2) 内循环执行 1 次。这将给出 (n-3) (n-2)/2。当我们考虑 if 条件和它的主体时，每次执行内部循环，都会执行 3 条语句。总共将给出 (n-3) (n-2)/2 * 3。不需要将 (n-3) 视为 (n-3)，而是将其视为 n 并且不考虑 **3和 /2。使用这种方法计算复杂度是一种近似值。所以复杂度是 n*n 的数量级。O(n^2)。

当您看到一个循环时，请将其视为 n 个步骤。如果有内部循环，则将其相乘。对于一个循环 O(n)。对于两个循环 O(n*n)。对于三个循环 O(n**n*n) 等。

于 2017-06-20T07:40:51.263 回答
0

像这样的问题似乎经常出现在这里。这是您的交换代码：

for (i=1; i < n-1; i++) {
    for (j=n; j > i+1; j--) {
        if (a[j-1] > a[j]) {
            t = a[j-1];
            a[j-1] = a[j];
            a[j] = t;
        }
    }
}

感谢外部循环将采取N-1措施。内部循环将在N-2和1步骤之间进行。我们可以通过说外循环有N步骤而内循环将在 1 和N步骤之间进一步近似这一点。平均而言，内部循环将采取N/2步骤完成。

这适用于O(N*N/2)= O(N^2)。因此，您向我们展示的交换代码是O(N^2).

于 2017-06-20T07:17:05.743 回答