我正在学习算法课程,并且希望对以下问题有所帮助:
以下数组[k+1,...,n,1,...,k]
的时间复杂度是多少,其中k>n/2
,并且枢轴始终被选择为子数组的最右边的单元格?
是O(n²)
还是O(nlgn)
?
[根据过去学期的扫描算法测试,学生说O(n²)
(我在几次模拟后都同意),但没有给出解释就得出了错误的答案。当我们三个人自己得出相同的结论时,我和一对学生对为什么答案是错误的感到困惑。
O(n²)是正确的。
[第一次运行将选择最右边的元素k
作为枢轴,将数组的其余部分分成左侧的[1, ..., k-1]
和右侧的[k+1, ..., n]
。由于这两个子数组都按排序顺序排列,因此它们的形式是快速排序选择最右边的元素作为枢轴需要二次时间。
因此,对分区的左侧进行排序将花费O(k²)时间,对右侧进行排序将花费O((n-k)²)时间。由于我们有n/2 < k <= n
,所以我们也有O(k²)= O(n²)。