WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
算法基础简介
枚举
模拟
递归 & 分治
贪心
排序简介
选择排序
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序
堆排序
桶排序
希尔排序
锦标赛排序
排序相关 STL
排序应用
前缀和 & 差分
二分
倍增
22 objects
本站非官方,所收集资源均来源于网络。
排序应用 - 算法基础
本页面将简要介绍排序的用法。 ## 降低时间复杂度 使用排序预处理可以降低求解问题所需要的时间复杂度。 ### "示例:检查给定数列中是否有相等的元素" > 考虑一个数列,你需要检查其中是否有元素相等。 > > 一个朴素的做法是检查每一个数对,并判断这一对数是否相等。时间复杂度是 $O(n^2)$ 。 > > 我们不妨先对这一列数排序,之后不难发现:如果有相等的两个数,它们一定在新数列中处于相邻的位置上。这时,只需要 $O(n)$ 地扫一遍新数列了。 > > 总的时间复杂度是排序的复杂度 $O(n\log n)$ 。 ## 作为查找的预处理 排序是 [二分查找](#) 所要做的预处理工作。在排序后使用二分查找,可以以 $O(\log n)$ 的时间在序列中查找指定的元素。