排序算法时间复杂度

 我来答
热爱旅游知识
高粉答主

2022-11-25 · 喜欢旅游知识,对历史有研究。
热爱旅游知识
采纳数:255 获赞数:44602

向TA提问 私信TA
展开全部

排序算法的时间复杂度是若文件的初始状态是正序的,一趟扫描即可完成排序。

比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的。

各种常用的算法,对时间复杂度的情况是这样。直接插入排序,是n平方的时间复杂度。直接选择排序是n平方的时间复杂度,冒泡排序也是n平方的时间复杂度。快速排序,希尔排序,和归并排序,都是n×(logn)的时间复杂度。

次线性时间

对于一个算法,若其匹配T(n) = o(n),则其时间复杂度为次线性时间(sub-linear time或sublinear time)。实际上除了匹配以上定义的算法,其他一些算法也拥有次线性时间的时间复杂度。例如有O(n)葛罗佛搜索算法。

推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式