对于一个长度为n的无序整数数组进行原地排序(in-place sort),以下关于空间复杂度的描述,哪一项最为准确地刻画了算法的存储需求特性?

答案解析

选项A错误,虽然原地排序强调在原数组上操作,但递归排序算法(如快速排序、归并排序的递归实现)会使用函数调用栈,因此空间复杂度并非始终为O(1)。选项B正确,递归排序算法(特别是快速排序和归并排序的递归版本)在最坏情况下需要O(n)的栈空间。选项C错误,复制一份数组进行排序并非原地排序的特征,且即便进行复制,空间复杂度也可能达到O(n)。选项D错误,空间复杂度与效率相关不总是成立,并且对原地排序算法,其空间复杂度通常不是log n,且快速排序的递归栈深度最坏可能是O(n)。
正确答案:B
随机推荐
开始刷题