排序应用


本页面将简要介绍排序的用法。

理解数据的特点

使用排序处理数据有利于理解数据的特点,方便我们之后的分析与视觉化。像一些生活中的例子比如词典,菜单,如果不是按照一定顺序排列的话,人们想要找到自己需要的东西的时间就会大大增加。

计算机需要处理大规模的数据,排序后,人们可以根据数据的特点和需求来设计计算机的后续处理流程。

降低时间复杂度

使用排序预处理可以降低求解问题所需要的时间复杂度,通常是一个以空间换取时间的平衡。如果一个排序好的列表需要被多次分析的话,只需要耗费一次排序所需要的资源是很划算的,因为之后的每次分析都可以减少很多时间。

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

一个朴素的做法是检查每一个数对,并判断这一对数是否相等。时间复杂度是

我们不妨先对这一列数排序,之后不难发现:如果有相等的两个数,它们一定在新数列中处于相邻的位置上。这时,只需要 地扫一遍新数列了。

总的时间复杂度是排序的复杂度

作为查找的预处理

排序是

二分查找 所要做的预处理工作。在排序后使用二分查找,可以以 的时间在序列中查找指定的元素。

贡献者:@queenwen@mgt@Leo@夜轮_NachtgeistW@sshwy@partychicken

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组