c# - 冒泡排序最坏的例子是 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 秒或两周才能执行。