BubbleSort 的大 O 在一个包含 5 个值的简单列表上

Question

我相信 BubbleSort 的顺序为 O(n^2)。当我阅读以前的帖子时，这与嵌套迭代有关。但是当我干燥运行一个简单的未排序列表时，（见下文），我在 10 次比较中对列表进行了排序。

在我的示例中，这是我的整数值列表： 5 4 3 2 1

为了让 5 入位，我进行了 n-1 次交换操作。 (4)
为了让 4 到位，我进行了 n-2 次交换操作。 (3)
为了让 3 到位，我进行了 n-3 次交换操作。 (2)
为了让 2 就位，我进行了 n-4 次交换操作。 (1)

我看不出 (n^2) 是从哪里来的，因为当我有一个包含 n=5 项的列表时，我只需要 10 次交换操作。

顺便说一句，我已经看到 (n-1).(n-1) 这对我来说没有意义，因为这将进行 16 次交换操作。

为了简单明了，我只关心基本的 BubbleSort...一个简单的嵌套 FOR 循环。

Answer 1

如果您想精确地说有 (n)*(n-1)/2 操作，因为您实际上是在计算 n+(n-1)+(n-2)+...+1，因为第一个元素需要 n 次交换，第二个元素需要 n-1 次交换，并且很快。所以算法是O(1/2 * (n^2) - n)，在渐近符号中等于O(n^2)。但冒泡排序中实际发生的事情是不同的。在冒泡排序中，您对数组执行传递并交换放错位置的邻居位置，直到没有放错位置为止，这意味着数组已排序。由于数组的每次传递都需要 O(n) 时间，在最坏的情况下，您必须执行 n 次传递，因此算法是 O(n^2)。请注意，我们计算的是比较次数而不是交换次数。

维基百科中提到了两种版本的冒泡排序：

procedure bubbleSort( A : list of sortable items )

   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

此版本执行 (n-1)*(n-1) 比较 -> O(n^2)

Optimizing bubble sort
The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

此版本执行 (n-1)+(n-2)+(n-3)+...+1 操作，即 (n-1)(n-2)/2 比较 -> O(n^2)

Answer 2

你好像不太理解big O notation的概念出色地。它指的是操作次数或时间如何增长与输入大小的关系，渐进地，只考虑增长最快的项，并且不考虑常数比例.

像您的 5:10 这样的单一测量结果是完全没有意义的。想象一下，寻找一个将 5 映射到 10 的函数。它是 2N 吗？ N + 5？ 4N—— 10？ 0.4N²? N² – 15？ 4 日志₅N + 6？这可能性是无限的。

相反，您必须分析算法以查看操作随着 N 的增长而增长，或者测量许多操作或时间运行，使用 N 的各种值和您可以使用的最通用的数据集设计。请注意，您的测试用例根本不通用：检查时排序算法的平均性能，您希望输入是以随机顺序（最有可能的情况），未排序或反向排序。

BubbleSort 的大 O 在一个包含 5 个值的简单列表上

Big O of BubbleSort on a simple list of 5 values

algorithm

big-o