gpt4 book ai didi

complexity-theory - 为什么冒泡排序的复杂度是 O(n^2)?

转载 作者:行者123 更新时间:2023-12-01 22:40:27 24 4
gpt4 key购买 nike

据我了解,算法的复杂度是排序时执行的最大操作数。所以,冒泡排序的复杂度应该是算术级数(从 1 到 n-1)的和,而不是 n^2。以下实现计算比较次数:

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的等差数列之和。

那么为什么冒泡排序的复杂度是 n^2,而不是 S(n-1)?

最佳答案

这是因为大 O 表示法描述了算法的性质。 (n-1) * (n-2)/2 展开式中的主要术语是 n^2。因此,随着 n 的增加,所有其他项都变得无关紧要。

欢迎您更准确地描述它,但出于所有意图和目的,该算法表现出 行为 的顺序为 n^2。这意味着如果您根据 n 绘制时间复杂度图,您将看到一条抛物线增长曲线。

关于complexity-theory - 为什么冒泡排序的复杂度是 O(n^2)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14843486/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com