文章
133
粉丝
0
获赞
0
访问
13.4k

评分及理由
(1)得分及理由(满分5分)
学生答案中描述了大根堆算法思想:建立大小为10的大根堆,遍历剩余元素,若元素小于堆顶则替换堆顶并调整堆,最终堆中即为最小的10个数。这与标准答案中的方法二完全一致,算法思想正确且描述清晰。因此得5分。
(2)得分及理由(满分5分)
学生答案给出的时间复杂度为O(nlog₂n),但标准答案中堆方法的时间复杂度为O(n)。因为建堆时间为O(k),每次堆调整时间为O(log k),共调整n-k次,总时间复杂度为O(k + (n-k)log k) = O(n log k),其中k=10为常数,所以实际为O(n)。学生写成O(nlog₂n)存在轻微误差,但考虑到k=10是常数,O(n log k)与O(n)在渐进意义下等价,且题目强调平均情况比较次数尽可能少,堆方法确实能达到线性时间复杂度,因此不扣分。空间复杂度O(1)正确。得5分。
题目总分:5+5=10分
登录后发布评论
暂无评论,来抢沙发