文章
63
粉丝
0
获赞
0
访问
13.0k
(1)由于我们需要找出M中最小的10个数,所以我们可以采用堆排序的思想,将数组中的元素变成一个小根堆,则每次根节点就是目前数组当中最小的元素;我们每次取出根节点的数字,然后调整小根堆,又会得到第二小的数字,以此类推,经过10次,我们可以得到M中最小的10个数。
(2)空间复杂度即堆的大小为O(n),时间复杂度即建堆的时间+10*调整堆的时间,即O(logn)。
评分及理由
(1)得分及理由(满分5分)
得分:2分
理由:学生使用了小根堆的思路,但算法描述存在逻辑错误。题目要求找到最小的10个数,使用小根堆需要先构建整个数组的小根堆(时间复杂度O(n)),然后连续10次取出堆顶元素(每次调整堆O(logn)),总共需要O(n + 10logn)时间。但这种方法需要修改原数组,且空间复杂度为O(1)。然而,标准答案中使用的是大根堆来维护最小的10个数,这种方法只需要O(nlog10)的时间复杂度,效率更高。学生的算法虽然能正确得到结果,但效率不如标准答案,且没有说明如何维护最小的10个数,而是直接构建整个堆,这在n很大时效率较低。
(2)得分及理由(满分5分)
得分:1分
理由:学生分析的时间复杂度和空间复杂度存在错误。空间复杂度应为O(1)(原地算法),但学生写成了O(n)。时间复杂度分析也不准确,建堆时间为O(n),10次调整堆为O(10logn),总时间复杂度应为O(n + 10logn),但学生简化为O(logn),忽略了建堆的O(n)项。
题目总分:2+1=3分
登录后发布评论
暂无评论,来抢沙发