冒泡排序最坏的例子是O（n * n），怎么样？
我正在尝试冒泡排序。 有5个元素，数组未排序。 泡沫排序的最坏情况是O（n ^ 2）。
作为我正在使用的例子
A = {5,4,3,2,1}
在这种情况下，比较应该是5 ^ 2 = 25.使用手动validation和代码，我得到比较计数为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[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(); } } } 输出如下
- – > 45321
- – > 43521
- – > 43251
- – > 43215
- – > 34215
- – > 32415
- – > 32145
- – > 32145
- – > 23145
- – > 21345
- – > 21345
- – > 21345
- – > 12345
- – > 12345
- – > 12345
- – > 12345
- – > 12345
- – > 12345
- – > 12345
- – > 12345
知道为什么数学不会出现25？
Big-O表示法不会告诉您算法将花费多少次迭代（或多长时间）。 随着元素数量的增加（通常朝向无穷大），它表示函数的增长率。
因此，在您的情况下，O（n 2 ）只是意味着冒泡排序的计算资源以元素的数量增加。 所以，如果你有两倍的元素，你可以期望它（最坏的情况）4倍（作为一个上限 ）。 如果你有4倍的元素，复杂性会增加16倍。
对于具有O（n 2 ）复杂度的算法，五个元素可以进行25次迭代，或25,000次迭代。 没有分析算法就无法分辨。 同样，具有O（1）复杂度（恒定时间）的函数可能需要0.000001秒才能执行或执行两周。
如果算法需要n^2 - n运算，那么它仍然简化为O(n^2) 。 Big-O表示法只是算法缩放的近似值，而不是对特定输入所需的操作数的精确测量。
考虑一下：您的示例，对5个元素进行冒泡排序，需要进行5×4 = 20次比较。 这推广到N个元素的冒泡排序需要N x（N-1）= N ^ 2 – N比较，并且N ^ 2非常快地得到比N大的LOT。这就是O（N ^ 2）来自的地方。 （例如，对于20个元素，您正在查看380个比较。）
冒泡排序是一个特殊的情况，它的完整复杂性是（n *（n-1）） – 它给你正确的数字：5个元素导致5 *（5-1）操作，这是20，是你的在最坏的情况下发现。
然而，简化的Big O表示法删除了常数和最不显着增长的项，并且只给出了O（n ^ 2）。 这使得将其与其他可能不具有精确（n *（n-1））的实现和算法进行比较变得容易，但是当简化时显示工作如何随着更大的输入而增加。
比较Big O表示法要容易得多，对于大型数据集，常量和较小的术语可以忽略不计。
请记住，O（N ^ 2）是从C * N（2）的实际表达式简化而来的; 也就是说，有一个有界的常数。 例如，对于冒泡排序，C大约为1/2（不完全，但接近）。
我认为你的比较计数也是关闭的，它应该是10次成对比较。 但我想你可以考虑将元素交换成另一个元素。 无论哪种方式，所做的只是改变常数，而不是更重要的部分。
for (int i=4; i>0; i--) { for (int j=0; jA[j+1]){ swapValues(A[j],A[j+1]); ................
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