插入排序的具体运行时复杂性是什么

Question

我只是介绍一些基本的排序算法。我实现了以下插入排序。

public static int[] insertionSort(int[] arr){
int I = 0;
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < i; j++){
if(arr[i] < arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

}
I++;
}
}
System.out.println(I);
return arr;
}

CCD_ 1针对具有100个随机生成的整数的大小为100的阵列打印出4950。

我知道这个算法被认为是O(n^2(，但在算术上更正确的运行时是什么？如果它真的是O(N^2(I，我假设它会打印出10000而不是4950。

Answer 1

Big Oh表示法告诉我们，随着输入大小的增大，算法必须做多少工作。单个输入测试并不能提供足够的信息来验证理论上的"大哦"。您应该在100到100万个不同大小的数组上运行该算法，并将数组的大小作为x变量，将代码输出的步数作为y变量，绘制输出图。当你这样做的时候，你会看到这个图是一个抛物线。

您可以使用代数来获得形式为y = a*x^2 + b*x +c的函数，该函数尽可能接近此数据。但是使用Big Oh表示法，我们不关心较小的项，因为与x^2部分相比，它们变得微不足道。例如，当x = 10^3时，则x^2 = 10^6比b*x + c大得多。如果x = 10^6，那么x^2 = 10^12也比I0大得多，我们可以忽略这些较小的项。

Answer 2

您可以进行以下观察：在外循环的第i次迭代中，内循环运行i次，i从0到n-1，其中n是数组的长度。

在整个算法上，内环总共运行T(n(次，其中

T(n) = 0 + 1 + 2 + ... + (n-1)

这是一个算术级数，很容易证明和等于n:上的二次多项式

T(n) = n*(n-1)/2 = .5*n^2 - .5*n

对于n=100，公式预测内部循环将运行T(100(=100*99/2=4950次，这与您的计算结果相匹配。