转自作业帮https://www.zybang.com/question/a12eaf411fa8085fd93d4a3756fbee75.html

有很多算法,复杂度也不尽相同.以下简单举几个例子：
1.n×m遍扫描
【算法基本描述】n×m遍扫描
【算法思想】每次都扫描一遍数组,取出最大元素,这样扫描m遍就能得到m个最大的数
【算法复杂度】O(nm)
2.排序后取最大m个数
【算法基本描述】对n个数排序,对拍完序后的序列取m个最大的数
【算法复杂度】视排序的复杂度,一般为O(nlogn)或O(n^2)
3.最小堆
【算法基本描述】一遍扫描+最小堆
【算法伪代码】
00-建立一个最小堆（优先队列）,最小堆的大小控制在m之内
01-for 每个数：
02-----if 这个数比最小堆的堆顶元素大：
03---------弹出最小堆的最小元素
04---------把这个数插入到最小堆
05-最小堆中的m个元素就是所要求的元素
06-其中最小堆的作用就是保持里面始终有m个最大元素,且m个元素中最小的元素在堆顶.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

O(nlogm) 遍历O(n) 最小堆O(logm)
4.

链接：https://www.nowcoder.com/questionTerminal/dfe1f8e38d1f47909ea48e1c8592ac75?pos=60&orderByHotValue=1

来源：牛客网

1.最简单的方法：将n个数排序，排序后的前k个数就是最大的k个数，这种算法的复杂度是O（nlogn） 2.O（n）的方法：利用快排的patition思想，基于数组的第k个数来调整，将比第k个数小的都位于数组的左边，比第k个数大的都调整到数组的右边，这样调整后，位于数组右边的k个数最大的k个数(这k个数不一定是排好序的） 比如（3,5,8,1,6,4） 取3个最大数，那我以最后一个数4为分割，可能得到（3,1,4，5，6,8），如果4是最大三个中的一个，那么4的右边应该有两个数，，否则，如果大于两个数往右区间找，小于往左区间找，这样的结果就是，n+n/2(未必是n/2但是n/3,n/4都是可能的)+n/4.。。,最后的复杂度一定是kn+c的，（1<k<2）因此是O（n）的     看到网上有的说是最小复杂度是O（n），有的答案说是O(mlogn）， 我觉得都不对，这取决于m和n之间的关系， 当m远小于n的时候，当然是O(mlogn）更小， 但是如果m和n相差不是很大，那么明显是O（n）更小    
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄