从n个数值选出最大的m个数（3mn），其最小算法复杂度是

[不定项选择题]

从n个数值选出最大的m个数（3<m<n），其最小算法复杂度是:

```
 O(nlogn)
```
```
O(mn)
```
```
O(logn)
```
```
 O(n)
```

查看正确选项

希望被offer砸中200

计数排序一次遍历数组记录出现次数O(n)，倒过来变量计算m个。

发表于 2021-09-01 09:23:52 回复(0)

天末凉风，蒹葭苍苍

为什么选O（n）,转载CSDN

BFPRT算法步骤如下：

（1）：选取主元；
（1.1）：将n个元素划分为⌊n/5⌋个组，每组5个元素，若有剩余，舍去；
（1.2）：使用插入排序找到⌊n/5⌋个组中每一组的中位数；
（1.3）：对于（1.2）中找到的所有中位数，调用BFPRT算法求出它们的中位数，作为主元；
（2）：以（1.3）选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；
（3）：判断主元的位置与k的大小，有选择的对左边或右边递归。

简单来说，就是将原始数据分成5组每组求一个中位数，这样求出n/5个中位数，对于这些中位数递归调用BFPRT算法求其中位数，以该中位数作为主元进行划分，再判断划分之后的位置进行下一次递归。

时间复杂度分析：
BFPRT算法在最坏情况下的时间复杂度是O(n)，下面予以证明。
首先将n个元素分成5个元素一组将分成n/5组，对于每一组的5个元素求出中位数，这里有n/5组，每组只有5个数无论采用什么样的方式5个数当中求出中位数的复杂度为o(1)，因为这里有n/5组，所以这里的复杂度为o(n)。
对求出的这n/5个中位数递归调用BFPRT算法求其中位数的复杂度为T(n/5)，相同的问题规模是原来的5分之1。
将得到的中位数作为下次partion的主元，此时对于partion进行分析：
因为该主元是得到的n/5个中位数的中位数所以至少大于其中1/2个中位数，所以主元大于1/2 * n/5 = n/10个中位数，每个中位数是原本5个元素当中的中位数所以每个中位数至少大于等于其中的3个数所以，我们选取的主元将至少大于等于n/10 * 3= 3n/10个元素，同理也将小于等于3n/10个元素，这也就避免了最坏的区分。我们假设每次运气最差都是选择到的是7n/10的那个区域此时问题将缩小至T(7n/10)。

所以总体的时间复杂度为： T(n) = T(n/5) + T(7n/10) + O(n)
计算可得： T(n) = 10O(n) = O(n)。
————————————————
版权声明：本文为CSDN博主「zhc_24」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zhc_24/article/details/82250774

发表于 2022-09-20 16:59:58 回复(0)

提交观点

问题信息

小米集团测试开发工程师 2021

上传者：小小

难度：

2条回答 33收藏 588浏览

从n个数值选出最大的m个数（3mn），其最小算法复杂度是

问题信息

热门推荐

相关试题