问题描述
据我了解,算法的复杂性是排序时执行的最大操作数.因此,冒泡排序的复杂度应该是算术级数的总和(从1到n-1),而不是n ^ 2.以下实现计算比较次数:
As I understand, the complexity of an algorithm is a maximum number of operations performed while sorting. So, the complexity of Bubble sort should be a sum of arithmmetic progression (from 1 to n-1), not n^2.The following implementation counts number of comparisons:
public int[] sort(int[] a) {
int operationsCount = 0;
for (int i = 0; i < a.length; i++) {
for(int j = i + 1; j < a.length; j++) {
operationsCount++;
if (a[i] > a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
System.out.println(operationsCount);
return a;
}
包含10个元素的数组的输出为45,因此它是从1到9的算术级数之和.
The ouput for array with 10 elements is 45, so it's a sum of arithmetic progression from 1 to 9.
那么为什么冒泡排序的复杂度是n ^ 2,而不是S(n-1)?
So why Bubble sort's complexity is n^2, not S(n-1) ?
推荐答案
这是因为big-O表示法描述了算法的性质.扩展(n-1) * (n-2) / 2
中的主要术语是n^2
.因此,随着n
的增加,所有其他术语变得无关紧要.
This is because big-O notation describes the nature of the algorithm. The major term in the expansion (n-1) * (n-2) / 2
is n^2
. And so as n
increases all other terms become insignificant.
欢迎您对其进行更精确的描述,但是出于所有意图和目的,该算法表现出的行为的顺序为n^2
.这意味着,如果根据n
绘制时间复杂度,则会看到一条抛物线的增长曲线.
You are welcome to describe it more precisely, but for all intents and purposes the algorithm exhibits behaviour that is of the order n^2
. That means if you graph the time complexity against n
, you will see a parabolic growth curve.
这篇关于为什么冒泡排序复杂度是O(n ^ 2)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!