如何根据Big O表示法找到此代码的复杂性？

我在我的算法书上发现了这个代码，但我无法理解这个例子。如何根据Big O表示法找到此代码的复杂性？

下面是代码：

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

对不起我的英文。

来源

2017-06-20 Snxby

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

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-20 07:17:05

外循环执行i = 1到n-2，即n-2次。内循环执行总共n-3 + n-4 + n-5 + ... +（n-3），（n-4） 2 + 1次。当i = 1内循环执行（n-3）次时，当i =（n-2）内循环执行1次时。这将给（n-3）（n-2）/ 2。当我们考虑if条件和它的body时，对于每个内循环的执行，执行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-20 07:40:51

如何根据Big O表示法找到此代码的复杂性？

回答

相关问题