搜索

C语言实现快速查找给定一数组第N大的数。要求算法时间复杂度不得

gecimao 发表于 2019-06-12 17:22 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  2013-05-16展开全部快速排序、堆排序、归并排序的时间复杂度为O(nlgn)。

  用任意一种算法实现后,然后根据所输入的第N大的这个N,选择对应下标(N-1的位置)的数进行输出。更多追问追答追问快速排序的时间复杂度在最坏的情况下应该是O(n*n)吧?

  是否能实现比O(nlgn)更快的呢? 比如线性时间内?追答平均的话,快速排序、堆排序、归并排序的时间复杂度为O(nlgn)。

  如果说比O(nlgn)更快,平均时间里面没有符合要求的了。最快就是O(nlgn)。

  (虽然最快的情况下插入排序和气泡排序O(n))。追问我刚刚查了一下, 可实现在平均情况下O(n)复杂度的查找。 方法如下:

  1. 对数组进行一下快速排序的划分, 也就是使k ( 0 = k = n) 前面的元素都小于a[k], k后面的元素都大于a[k]. 这样一次可丢弃n- k或 k个数据, 如此方式进行递归, 很快可找到第i小的元素。

本文链接:http://baumseelen.com/duipaixu/572.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部