文章
119
粉丝
0
获赞
1
访问
10.0k
评分及理由
(1)得分及理由(满分4分)
得2分。学生的基本设计思想是先对整个数组进行快速排序,然后取前一半和后一半分别求和,对于奇数个元素的情况,尝试将中间元素加入前一半或后一半,取绝对值较大的差值。这个思路可以满足题目要求,但效率较低,因为需要完全排序整个数组,而标准答案采用基于快速选择的部分划分,平均时间复杂度为O(n)。学生的思路虽然正确但不够高效,因此扣2分。
(2)得分及理由(满分9分)
得5分。学生实现了快速排序和划分函数,但代码存在以下问题:
1. 快速排序函数缺少递归终止条件(如l>=r),这会导致无限递归,属于逻辑错误,扣2分。
2. 划分函数中,内层循环条件重复(外层while已检查l
4. 代码未实现标准答案中基于枢轴的高效划分方法,而是完全排序,效率较低,但功能正确,扣1分。
总体代码能实现功能,但存在逻辑错误和效率问题,因此扣4分。
(3)得分及理由(满分2分)
得1分。学生正确给出了时间复杂度O(nlog₂n)和空间复杂度O(log₂n)(快速排序的递归栈深度),但标准答案要求的是平均O(n)时间复杂度和O(1)空间复杂度。学生的算法复杂度高于标准答案,因此扣1分。
题目总分:2+5+1=8分
登录后发布评论
暂无评论,来抢沙发