同学面试得到的题目,求n(n=100)个数中第5大的数最快速的算法面试官给的答案是,用堆排序,建5个数的堆,然后将余下的数替换进去,进行调堆算法n次,复杂度为nlog5,那为什么不可以对n个数建堆

来源:学生作业帮助网 编辑:作业帮 时间:2024/04/24 22:17:32
同学面试得到的题目,求n(n=100)个数中第5大的数最快速的算法面试官给的答案是,用堆排序,建5个数的堆,然后将余下的数替换进去,进行调堆算法n次,复杂度为nlog5,那为什么不可以对n个数建堆

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

同学面试得到的题目,求n(n=100)个数中第5大的数最快速的算法面试官给的答案是,用堆排序,建5个数的堆,然后将余下的数替换进去,进行调堆算法n次,复杂度为nlog5,那为什么不可以对n个数建堆
你把建堆的消耗忽略了,
你建堆的过程时间复杂度是O(n),然后调用5次时间复杂度为5O(logn),相当于O(n)+5O(logn) = O(n)

同学面试得到的题目,求n(n=100)个数中第5大的数最快速的算法面试官给的答案是,用堆排序,建5个数的堆,然后将余下的数替换进去,进行调堆算法n次,复杂度为nlog5,那为什么不可以对n个数建堆 四边形性质题目1 一个n边形的(n-1)个内角的和是1000度,那么,n=?另外的那一个内角=?写出计算式子(2)1个同学在计算多边形的内角和时,多加了一个内角,结果得到的和是1300度,那么,n=?多加的那 刘老师您好,想向您请教一道线性代数题目,谢谢已知二阶方阵A= [3 9] [1 3]求A^n.(其中A^n表示n个A相乘得到的方阵) 二项式的题目1/(C5,n)-1/(C6,n)=0.7/(C7,n)求(C8,n)(C8,n)表示从8个数字中拿出5个组合 初等数论题目求所有正整数 n,使 7 ^ n | 9 ^ n - 1(n ^ m = n 的 m 次方). 一道数学题(线性代数)已知二阶方阵A= [3 9][1 3]求A^n.(其中A^n表示n个A相乘得到的方阵) 一道数学线性代数题已知二阶方阵A= [3 9][1 3]求A^n.(其中A^n表示n个A相乘得到的方阵) 一道数列求和的题目已知an=(2n+1)2n求Sn 请教个数字信号处理的题目设x(n),y(n)分别为两个N点序列,又设f(n)=x(n)+jy(n)且已求得F(k)=DFT(f(n))=1+j2,求X(k)=DFT(x(n)) Y(k)=DFT(y(n)) 以及x(n)和y(n). 求使2^n-1+n*[2^(n+1)]>2000成立的自然数n的最小值那个,同学,是(2^n)-1,不是2^(n-1) 比较难的求极限题目(只要思路) 为什么lim(n趋向于无穷)1/n*{(n+1)(n+2).(n+n)}^(1/n)=4/e? 关于证明极限的题目中2^n=(1+1)^n>=n(n-1)/2是怎么得到的, 数学题目: 求1/(n*n-1)的前n项和,第一项n=2开始. 已知方程(n²+n+1)^(n²+14n)=(n²+n+1)^(3n-9),求满足方程的n有()个.要求有完整过程, 第一个:设liman=A(n为下标,趋近于无穷大),那么有a1+a2+...+anlim—————— =An 第二个:设a =n!的n次方根/n,求lima (n趋于无穷大)n n看来是我没有把题目说清楚 第一题是个证明题第二个题目前面 求1N、2N、3N ……..100N.2055N,这101个力的合力最小值 Pascal题目:线段总长时间限制:1 Sec 内存限制:32 MB数轴上有N个点,任意两点连线得到n(n-1)条线段,试求线段的总长.输入第一行,一个整数N,表示点数.接下来N行,每行一个整数X_i,表示点的坐标.输出 有2n个数,其中n个0,n个1.随机排成一行,求没有两个1连在一起的概率.(n+1)(n!)(n!)/(2n!) 或(n+1)/(2n)C(n)