冒泡排序最坏的例子是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