1

如果我有一个数组,其中单元格 0-N 已排序,单元格 N+1 直到 M+N,未排序。对数组进行排序的最佳时间复杂度是多少?

谢谢!


编辑:

谢谢 !!如果我想就地这样做,它会改变复杂性吗?

4

1 回答 1

4

首先,只对 M 个未排序的元素进行排序。这需要时间 O(M log M) 使用基于比较的排序(如快速排序、合并排序或堆排序)。

然后将两个排序的段(长度为 N 和 M)合并在一起。这需要时间 O(M + N)。

所以最好的时间复杂度,使用基于比较的排序,是 O(M + N + M log M)。

于 2013-02-02T00:31:49.703 回答