2.3.11

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

只有若干种元素值意味着大量的连续重复。
(由于存在打乱这一步骤,不存在连续重复的可能性是很低的)
接下来我们考虑这样的连续重复在修改后的快排下的性能。
1 1 1 1 1 1 1
对于这样的数组,枢轴选为 1,j 将会在 j = lo 处终止。
因此最后的结果将是每次只有数组的第一个元素被排序
已知每次切分都是 O(k - 1) 的(i 和 j 都将走完整个子数组)
因此这样的快速排序所需时间 = $ 2 (N - 1 + N - 2 + \cdots + 1) = (N - 1)N $
因此对于值相同的子数组,这样的快排运行时间是平方级别的
那么当数组中这样的连续重复内容越多,运行时间就越接近平方级别。

上一题 下一题