文章
394
粉丝
0
获赞
0
访问
84.3k
1):我们利用大根堆,先取10个数然后维护大根堆,判断第11个数和大根堆堆顶元素的大小关系如果小于那就将它替换成堆顶元素,并更新大根堆,一直到n个数遍历完毕,此时堆里就是n个数中最小的10个数;
2):时间复杂度:o(nlogn),空间复杂度:o(1);
评分及理由
(1)得分及理由(满分5分)
学生描述了使用大根堆来查找最小的10个数的算法思想:先取前10个数构建大根堆,然后遍历剩余元素,若当前元素小于堆顶则替换堆顶并调整堆,最终堆中即为最小的10个数。该思路正确,与标准答案中的方法二一致,且描述清晰。因此,本小题得满分5分。
(2)得分及理由(满分5分)
学生给出的时间复杂度为O(nlogn),空间复杂度为O(1)。空间复杂度正确,因为算法只使用了常数额外空间。但时间复杂度分析有误:构建10个元素的大根堆耗时O(1),遍历剩余n-10个元素,每次堆调整(堆大小为10)耗时O(log10)=O(1),因此总时间复杂度应为O(n),而非O(nlogn)。此处属于逻辑错误,需扣1分。本小题得4分。
题目总分:5+4=9分
登录后发布评论
暂无评论,来抢沙发