DSA 冒泡排序时间复杂度

请查看 上一页 了解时间复杂度的一般解释。

冒泡排序时间复杂度

冒泡排序算法 在最坏情况下会遍历 \(n\) 个值的数组 \(n-1\) 次。

算法第一次遍历数组时，会将每个值与下一个值进行比较，如果左侧的值大于右侧的值，则交换这两个值。这意味着最大的值会冒泡到顶部，未排序部分的数组会越来越短，直到排序完成。因此，平均来说，在算法遍历数组比较和交换值时，会考虑 \(\frac{n}{2}\) 个元素。

我们可以开始计算冒泡排序算法在 \(n\) 个值上执行的操作次数。

\[操作次数 = (n-1)\cdot \frac{n}{2} = \frac{n^2}{2} - \frac{n}{2} \]

当查看算法的时间复杂度时，我们会关注非常大的数据集，这意味着 \(n\) 是一个非常大的数字。对于一个非常大的数字 \(n\)，\(\frac{n^2}{2}\) 项会比 \(\frac{n}{2}\) 项大得多。事实上，大到我们可以简单地去除第二项 \(\frac{n}{2}\) 来进行近似。

\[操作次数 = \frac{n^2}{2} - \frac{n}{2} \approx \frac{n^2}{2} = \frac{1}{2} \cdot n^2 \]

当我们使用大 O 符号查看时间复杂度时，会忽略系数，因此会省略系数 \(\frac{1}{2}\)。这意味着冒泡排序算法的运行时间可以用大 O 符号表示，如下所示。

\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

描述冒泡排序时间复杂度的图表如下所示。

如您所见，当数组的大小增加时，运行时间会非常快地增加。

幸运的是，有一些排序算法比它更快，例如 快速排序。

冒泡排序模拟

选择数组中值的个数，并运行此模拟，以查看冒泡排序在 \(n\) 个元素的数组上需要执行的操作次数为 \(O(n^2)\)。

上面的红线代表上限时间复杂度 \(O(n^2)\)，在本例中实际函数为 \(1.05 \cdot n^2\)。

如果存在一个正的常数 \(C\)，使得当 \(n\) 的值很大时 \(C \cdot g(n)>f(n)\)，则称函数 \(f(n)\) 为 \(O(g(n))\)。

在本例中，\(f(n)\) 是冒泡排序使用的操作次数，\(g(n)=n^2\)，\(C=1.05\)。

详细了解大 O 符号和时间复杂度，请访问 此页面。