Hi I am using the following generic bubble sort algorithm and I would like to display the time complexity. I understand that the best/worst case for this algorithm is fixed but I was wondering, can it be specific for my array?
嗨我使用以下通用冒泡排序算法，我想显示时间复杂度。我知道这个算法的最佳/最坏情况是固定的，但我想知道，它可以特定于我的阵列吗？
For example the worst case for this sort is O(n^2), can that be specific for my array?
例如，这种最坏的情况是O（n ^ 2），这可能是我的阵列特有的吗？
For example, worst case can be sorting 100 of the 120 elements (thats what i mean by specific for my array).
例如，最糟糕的情况是可以对120个元素中的100个进行排序（这就是我的数组特定的含义）。
public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
boolean changed = false;
do {
changed = false;
for (int a = 0; a < comparable.length - 1; a++) {
if (comparable[a].compareTo(comparable[a + 1]) > 0) {
E tmp = comparable[a];
comparable[a] = comparable[a + 1];
comparable[a + 1] = tmp;
changed = true;
}
}
} while (changed);
}
4 个解决方案
#1
6
Complexity is an asymptotic property of a function (or an algorithm), and not of an actual execution path. Complexity expresses the relation between input size and computation time (or space requirement). As such, this concept has no meaning when applied to one single, concrete computation.
复杂性是函数（或算法）的渐近属性，而不是实际执行路径的渐近属性。复杂性表示输入大小和计算时间（或空间要求）之间的关系。因此，当应用于单个具体计算时，该概念没有意义。
In other words, you can ask about the complexity of computing f(n) depending on n, but not of computing f(5). The latter is just a number. The former is a function.
换句话说，你可以询问计算f（n）的复杂性取决于n，而不是计算f（5）。后者只是一个数字。前者是一个功能。
What you can do instead is count the actual number of operations. Every time you perform an operation that you want to include (for example "comparisons"), just increment some global counter, and check its value afterwards. (The algorithmic complexity should tell you bounds for the values that this counter may take.)
你可以做的是计算实际的操作次数。每次执行要包含的操作（例如“比较”）时，只需递增一些全局计数器，然后检查其值。 （算法的复杂性应该告诉你这个计数器可能采用的值的界限。）
#2
3
The "worst case" performance of an algorithm refers to a set of input data that makes the algorithm behave most badly. So it doesn't make sense to refer to the "worst case" of a specific input array, because that is only one case.
算法的“最坏情况”性能是指一组输入数据，这使得算法表现得最糟糕。因此，引用特定输入数组的“最坏情况”是没有意义的，因为这只是一种情况。
#3
1
In the general case, your algorithm's worst-case complexity is O(n^2) (i.e. no more than n^2, asymptotically). It is also Theta(n^2) (i.e. no more and no less than n^2). I am omitting the multiplicative constant.
在一般情况下，您的算法的最坏情况复杂度为O（n ^ 2）（即，渐近地不超过n ^ 2）。它也是Theta（n ^ 2）（即不多于且不小于n ^ 2）。我省略了乘法常数。
Let's say you know something about your array. To keep things specific, let's say you know that your array requires no more than five bubblesort-type swaps to become sorted. With this knowledge, it is still correct to say that the run-time of your algorithm is O(n^2). It is, however, no longer Theta(n^2).
假设你对阵列有所了解。为了保持特定的内容，假设您知道您的数组需要不超过五个bubblesort类型的交换才能排序。有了这些知识，说算法的运行时间为O（n ^ 2）仍然是正确的。然而，它不再是Theta（n ^ 2）。
It is also correct to say that the run-time of the algorithm in that specific case is O(n). In other words, knowing something about the array has enabled us to provide a tighter bound on the runtime of your algorithm.
在该特定情况下算法的运行时间是O（n）也是正确的。换句话说，了解数组的某些内容使我们能够对算法的运行时提供更严格的约束。
#4
0
The best case for bubble sort occurs when the list is already sorted or nearly sorted O(n), so yes it can depend on your array.
当列表已经排序或几乎排序为O（n）时，会出现冒泡排序的最佳情况，所以是的，它可能取决于您的数组。
#1
6
Complexity is an asymptotic property of a function (or an algorithm), and not of an actual execution path. Complexity expresses the relation between input size and computation time (or space requirement). As such, this concept has no meaning when applied to one single, concrete computation.
复杂性是函数（或算法）的渐近属性，而不是实际执行路径的渐近属性。复杂性表示输入大小和计算时间（或空间要求）之间的关系。因此，当应用于单个具体计算时，该概念没有意义。
In other words, you can ask about the complexity of computing f(n) depending on n, but not of computing f(5). The latter is just a number. The former is a function.
换句话说，你可以询问计算f（n）的复杂性取决于n，而不是计算f（5）。后者只是一个数字。前者是一个功能。
What you can do instead is count the actual number of operations. Every time you perform an operation that you want to include (for example "comparisons"), just increment some global counter, and check its value afterwards. (The algorithmic complexity should tell you bounds for the values that this counter may take.)
你可以做的是计算实际的操作次数。每次执行要包含的操作（例如“比较”）时，只需递增一些全局计数器，然后检查其值。 （算法的复杂性应该告诉你这个计数器可能采用的值的界限。）
#2
3
The "worst case" performance of an algorithm refers to a set of input data that makes the algorithm behave most badly. So it doesn't make sense to refer to the "worst case" of a specific input array, because that is only one case.
算法的“最坏情况”性能是指一组输入数据，这使得算法表现得最糟糕。因此，引用特定输入数组的“最坏情况”是没有意义的，因为这只是一种情况。
#3
1
In the general case, your algorithm's worst-case complexity is O(n^2) (i.e. no more than n^2, asymptotically). It is also Theta(n^2) (i.e. no more and no less than n^2). I am omitting the multiplicative constant.
在一般情况下，您的算法的最坏情况复杂度为O（n ^ 2）（即，渐近地不超过n ^ 2）。它也是Theta（n ^ 2）（即不多于且不小于n ^ 2）。我省略了乘法常数。
Let's say you know something about your array. To keep things specific, let's say you know that your array requires no more than five bubblesort-type swaps to become sorted. With this knowledge, it is still correct to say that the run-time of your algorithm is O(n^2). It is, however, no longer Theta(n^2).
假设你对阵列有所了解。为了保持特定的内容，假设您知道您的数组需要不超过五个bubblesort类型的交换才能排序。有了这些知识，说算法的运行时间为O（n ^ 2）仍然是正确的。然而，它不再是Theta（n ^ 2）。
It is also correct to say that the run-time of the algorithm in that specific case is O(n). In other words, knowing something about the array has enabled us to provide a tighter bound on the runtime of your algorithm.
在该特定情况下算法的运行时间是O（n）也是正确的。换句话说，了解数组的某些内容使我们能够对算法的运行时提供更严格的约束。
#4
0
The best case for bubble sort occurs when the list is already sorted or nearly sorted O(n), so yes it can depend on your array.
当列表已经排序或几乎排序为O（n）时，会出现冒泡排序的最佳情况，所以是的，它可能取决于您的数组。