文章
427
粉丝
0
获赞
3
访问
66.0k
利用大根堆排序,每次选出十个数中最大的元素 依次遍历n个数后 堆中的十个数就是n个数中最小的十个
时间复杂度o(n)空间复杂度o(1)
评分及理由
(1)得分及理由(满分5分)
学生描述了使用大根堆的方法来查找最小的10个数,算法思想基本正确:维护一个大小为10的大根堆,堆顶是当前堆中最大的数,遍历后续元素,若比堆顶小则替换堆顶并调整堆。这与标准答案中的方法二一致。但描述过于简略,没有说明初始堆的构建过程(例如前10个元素如何形成大根堆),也没有提及遍历的起始位置(应从第11个元素开始比较)。鉴于核心思想正确,扣1分。得4分。
(2)得分及理由(满分5分)
学生给出的时间复杂度O(n)和空间复杂度O(1)是正确的。对于大根堆方法,建大小为10的堆是O(1),遍历n-10个元素,每次调整堆的代价是O(log 10)=O(1),因此总时间复杂度为O(n)。空间复杂度为原地操作,O(1)。因此得5分。
题目总分:4+5=9分
登录后发布评论
暂无评论,来抢沙发