C# 冒泡排序最坏的例子是 O(n*n)，如何？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1934636/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Bubble sort worst case example is O(n*n), how?
提问by bubbleQ
I am trying Bubble sort. There are 5 elements and array is unsorted. Worst case for bubble sort shuold be O(n^2).
我正在尝试冒泡排序。有 5 个元素，数组未排序。冒泡排序的最坏情况应该是 O(n^2)。
As an exmaple I am using
作为一个例子，我正在使用
A = {5, 4, 3, 2, 1}
A = {5, 4, 3, 2, 1}
In this case the comparison should be 5^2 = 25. Using manual verification and code, I am getting comparison count to be 20. Following is the bubble sort implemenation code
在这种情况下，比较应该是 5^2 = 25。使用手动验证和代码，我得到的比较计数为 20。以下是冒泡排序实现代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SortingAlgo
{
class Program
{
public static int[] bubbleSort(int[] A)
{
bool sorted = false;
int temp;
int count = 0;
int j = 0;
while (!sorted)
{
j++;
sorted = true;
for (int i = 0; i < (A.Length - 1); i++)
{
count++;
if(A[i] > A[i+1])
{
temp = A[i];
A[i] = A[i+1];
A[i+1] = temp;
sorted = false;
}
Console.Write(count + ". -> ");
for(int k=0; k< A.Length; k++)
{
Console.Write(A[k]);
}
Console.Write("\n");
}
}
return A;
}
static void Main(string[] args)
{
int[] A = {5, 4, 3, 2, 1};
int[] B = bubbleSort(A);
Console.ReadKey();
}
}
}
Output is following
输出如下
- -> 45321
- -> 43521
- -> 43251
- -> 43215
- -> 34215
- -> 32415
- -> 32145
- -> 32145
- -> 23145
- -> 21345
- -> 21345
- -> 21345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 45321
- -> 43521
- -> 43251
- -> 43215
- -> 34215
- -> 32415
- -> 32145
- -> 32145
- -> 23145
- -> 21345
- -> 21345
- -> 21345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
- -> 12345
Any idea why the maths its not coming out to be 25?
知道为什么数学结果不是 25 吗？
回答by StaxMan
Remember that O(N^2) is simplified from the actual expression of C * N(2); that is, there is a bounded constant. For bubble sort, for example, C would be roughly 1/2 (not exactly, but close).
请记住，O(N^2) 是从 C * N(2) 的实际表达式简化而来的；也就是说，存在一个有界常数。例如，对于冒泡排序，C 大约是 1/2（不完全是，但接近）。
Your comparison count is off too, I think, it should be 10 pairwise comparisons. But I guess you could consider swapping of elements to be another. Either way, all that does is change the constant, not the more important part.
您的比较计数也关闭了，我认为应该是 10 次成对比较。但是我想您可以考虑将元素交换为另一个。无论哪种方式，所做的只是改变常数，而不是更重要的部分。
回答by Robert Cartaino
Big-O notation doesn't tell you anything about how many iterations (or how long) an algorithm will take. It is an indication of the growth rateof a function as the number of elements increases (usually towards infinity).
Big-O 表示法并没有告诉你一个算法需要多少迭代（或多长时间）。它是生长的指示速度的函数的元素的增加（通常朝向无穷大）的数量。
So, in your case, O(n2) simply means that the bubble sort's computational resources grows by the square as the number of elements. So, if you have twice as many elements, you can expect it to take (worst case) 4-times as long (as an upperbound). If you have 4-times as many elements, the complexity increases by a factor of 16. Etc.
因此，在您的情况下， O(n 2) 仅意味着冒泡排序的计算资源随着元素数量的平方增长。所以，如果你有两倍的元素，你可以期望它（最坏的情况）需要 4 倍的时间（作为上限）。如果元素数量是原来的 4 倍，则复杂度会增加 16 倍。等等。
For an algorithm with O(n2) complexity, five elements could take 25 iterations, or 25,000 iterations. There's no way to tell without analyzing the algorithm. In the same vein, a function with O(1) complexity (constant time) could take 0.000001 seconds to execute or two weeks to execute.
对于复杂度为 O(n 2)的算法，五个元素可能需要 25 次迭代，或 25,000 次迭代。不分析算法就无法判断。同样，具有 O(1) 复杂度（恒定时间）的函数可能需要 0.000001 秒的执行时间或两周的执行时间。
回答by Bill the Lizard
If an algorithm takes n^2 - noperations, that's still simplified to O(n^2). Big-O notation is only an approximation of how the algorithm scales, not an exact measurement of how many operations it will need for a specific input.
如果算法需要n^2 - n操作，那仍然简化为O(n^2). Big-O 表示法只是算法扩展方式的近似值，而不是特定输入需要多少操作的精确度量。
回答by John R. Strohm
Consider: Your example, bubble-sorting 5 elements, takes 5x4 = 20 comparisons. That generalizes to bubble-sorting N elements takes N x (N-1) = N^2 - N comparisons, and N^2 very quickly gets a LOT bigger than N. That's where O(N^2) comes from. (For example, for 20 elements, you are looking at 380 comparisons.)
考虑：您的示例，冒泡排序 5 个元素，需要 5x4 = 20 次比较。这推广到冒泡排序 N 元素需要 N x (N-1) = N^2 - N 次比较，并且 N^2 很快变得比 N 大很多。这就是 O(N^2) 的来源。（例如，对于 20 个元素，您正在查看 380 个比较。）
回答by Adam Davis
Bubble sort is a specific case, and its fullcomplexity is (n*(n-1)) - which gives you the correct number: 5 elements leads to 5*(5-1) operations, which is 20, and is what you found in the worst case.
冒泡排序是一种特殊情况，它的完整复杂度是 (n*(n-1)) - 它为您提供正确的数字：5 个元素导致 5*(5-1) 次操作，即 20，这就是您在最坏的情况下发现。
The simplified Big O notation, however, removes the constants and the least significantly growing terms, and just gives O(n^2). This makes it easy to compare it to other implementations and algorithms which may not have exactly (n*(n-1)), but when simplified show how the work increases with greater input.
然而，简化的大 O 表示法去除了常数和增长最不显着的项，只给出 O(n^2)。这使得很容易将其与其他可能不精确 (n*(n-1)) 的实现和算法进行比较，但简化后显示工作如何随着输入的增加而增加。
It's much easier to compare the Big O notation, and for large datasets the constants and lesser terms are negligible.
比较大 O 符号要容易得多，对于大型数据集，常量和较小的项可以忽略不计。
回答by Fly
for (int i=4; i>0; i--) {
for (int j=0; j<i;j++) {
if (A[j]>A[j+1]){
swapValues(A[j],A[j+1]);
................
Comparison count for 5 (0:4) elements should be 10.
5 (0:4) 个元素的比较计数应为 10。
i=4 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3]) (j[3] j[4])} - 4 comparisons
i=3 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3])} - 3 comparisons
i=2 - {(j[0] j[1]) (j[1] j[2])} - 2 comparisons
i=1 - {(j[0] j[1])} - 1 comparison
