冒泡排序最坏的例子是O(n*n),怎么样？

Question

我正在尝试冒泡排序.有5个元素,数组未排序.泡沫排序的最坏情况是O(n ^ 2).

作为我正在使用的例子

A = {5,4,3,2,1}

在这种情况下,比较应该是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();
    }
   } 
  }

输出如下

1. - > 45321
2. - > 43521
3. - > 43251
4. - > 43215
5. - > 34215
6. - > 32415
7. - > 32145
8. - > 32145
9. - > 23145
10. - > 21345
11. - > 21345
12. - > 21345
13. - > 12345
14. - > 12345
15. - > 12345
16. - > 12345
17. - > 12345
18. - > 12345
19. - > 12345
20. - > 12345

知道为什么数学不会出现25？

Answer 1

Big-O表示法不会告诉您算法将采用多少次迭代(或多长时间).它是生长的指示速度的函数的元素的增加(通常朝向无穷大)的数量.

因此,在您的情况下,O(n ²)只是意味着冒泡排序的计算资源以平方增长为元素数量.所以,如果你有两倍的元素,你可以期望它(最坏的情况)4倍(作为一个上限).如果你有4倍的元素,复杂性会增加16倍.

对于具有O(n ²)复杂度的算法,五个元素可以进行25次迭代,或25,000次迭代.没有分析算法就没有办法说出来.同样,具有O(1)复杂度(恒定时间)的函数可能需要0.000001秒执行或执行两周.

Answer 2

如果算法采取n^2 - n操作,那仍然简化为O(n^2).Big-O表示法只是算法缩放的近似值,而不是对特定输入所需的操作数的精确测量.

Answer 3

考虑一下:您的示例,对5个元素进行冒泡排序,需要进行5x4 = 20次比较.这推广到N个元素的冒泡排序需要N x(N-1)= N ^ 2 - N比较,并且N ^ 2非常快地得到比N大的LOT.这就是O(N ^ 2)来自的地方.(例如,对于20个元素,您正在查看380个比较.)

Answer 4

冒泡排序是一种特殊情况，它的全部复杂度是 (n*(n-1)) - 它为您提供正确的数字：5 个元素导致 5*(5-1) 次操作，即 20，这就是您在最坏的情况下发现。

然而，简化的大 O 表示法去除了常数和增长最不显着的项，只给出 O(n^2)。这使得很容易将其与其他可能不精确 (n*(n-1)) 的实现和算法进行比较，但简化后显示工作如何随着输入的增加而增加。

比较大 O 符号要容易得多，对于大型数据集，常量和较小的项可以忽略不计。

Answer 5

请记住，O(N^2) 是从 C * N(2) 的实际表达式简化而来的；也就是说，存在一个有界常数。例如，对于冒泡排序，C 大约为 1/2（不完全是，但很接近）。

你的比较次数也少了，我想，应该是 10 两两比较。但我想你可以考虑将元素交换为另一个。不管怎样，所做的只是改变常数，而不是更重要的部分。