

排序应用

借助排序，我们可以降低求解问题所需要的时间复杂度。

考虑一个数列，你需要检查其中是否有元素相等。

一个朴素的做法是检查每一个数对，并判断这一对数是否相等。时间复杂度是 $O(n^2)$ 。

我们不妨先对这一列数排序，之后不难发现：如果有相等的两个数，它们一定在新数列中处于相邻的位置上。这时，只需要 $O(n)$ 地扫一遍新数列了。总的时间复杂度是排序的复杂度（ $O(n\log n)$ ）。

排序也是 二分查找 所要做的预处理工作。在排序后使用二分查找，我们可以在 $O(\log n)$ 的时间内在序列中查找指定的元素。

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论