同学面试得到的题目,求n（n=100）个数中第5大的数最快速的算法

来源：学生作业帮编辑：拍题作业网作业帮分类：数学作业时间：2024/04/30 20:02:33

同学面试得到的题目,求n（n=100）个数中第5大的数最快速的算法
面试官给的答案是,用堆排序,建5个数的堆,然后将余下的数替换进去,进行调堆算法n次,复杂度为nlog5,那为什么不可以对n个数建堆,进行5次调堆算法,求出第5大的数,算法复杂度为5logn,不是更小么,这样想有什么问题么,
对n个树建堆,一次调堆算法的复杂度跟堆的深度有关,而堆的深度大约是logn级别的,所以一次调堆的复杂度是logn,那求第5大的数,只需5次,那个复杂度是5logn,

你把建堆的消耗忽略了,
你建堆的过程时间复杂度是O(n),然后调用5次时间复杂度为5O(logn),相当于O(n)+5O(logn) = O(n)
再问：照你这么说，堆排序的算法复杂度应该不止nlogn吧？？
再答：堆排序,建堆O(n),依次出堆O(nlogn), O(n)+O(nlogn) = O(nlogn)

同学面试得到的题目,求n（n=100）个数中第5大的数最快速的算法计算概论C语言问题：如何求n个数中第k大的数 C语言,输入一个（1~20）的数n!得到n*n个数,以n*n矩阵顺时针输出! C语言 n个数中任意取两个数求和的算法求写出100个数中最小数的算法求莱布尼茨三角形的规律,如何快速求出第n行的第x个数?求公式! 有一列从小到大排列的数,其最小的数是-3,之后每一个数都比前一个数大2,最大的一个数是155.记第n个数是y,求y关于n 今天面试了一道题,请大家帮忙看下.一组数0.1.2.3.6.11.20.37.68用递归算法求第20个数的值. 一组按一定规律排列的数,则第n（n≥1）个数为? 按规律排了的一列数5.8.11.14.17.20..这数列中第十个数是多少第100个数是多少第n个数是多少有n个数,从第2个数开始,每个数都比它前面相邻的数大3,4,7,10,13,…,3n+1, 按规律排列的数4,8,16,32,.中,第N个数是多少?第2004个数是多少?