如何根据大 O 表示法找到这个嵌套 for 循环代码的复杂性？

Question

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

代码如下：

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

Answer 1

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

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

Answer 2

外层循环执行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) 等等

如何根据大 O 表示法找到这个嵌套 for 循环代码的复杂性？

How to find complexity of this nested for loop code according to Big O notation?

big-o

code-complexity