arrays - 排序与插入的 Big-O 运行时间

Question

因此，如果您使用快速排序对数组进行排序，您可以使用快速排序在 O(nlogn) 中进行排序，然后一旦对它进行排序，就可以使用二进制搜索式算法在 O(logn) 中将新元素插入数组中。

我的问题是，有没有办法证明如果你可以在 O(logn) 时间内插入一个排序数组，那么这意味着排序算法必须至少是 O(nlogn)？

换句话说，这两种算法的运行时间之间是否存在关系？

score 1 · Accepted Answer

否：可以使用冒泡排序 (O(n²)) 对数组进行排序。之后，仍然可以使用相同的算法在 O(log(n)) 时间插入。

score 1 · Accepted Answer

好吧，保持顺序的插入是 O(log n) 的事实意味着只需将每个元素依次插入数组中，就可以在 O(n log n) 中执行排序操作。但是，这可能与您真正要问的相反；它证明了存在 O(n log n) 排序，但并没有反驳更快排序的可能性。

score 0 · Accepted Answer

首先，一些需要特殊条件的排序算法可能具有较低的时间复杂度。例如复杂度为 O(n+k) 的计数排序（其中 k 是数组中的最高数字）或复杂度为 O(n*k) 的基数排序（其中 k 是数组中的最大位数元素）。
O(nlogn) 的界限适用于比较算法。

其次，回答这个问题，不（可悲）。插入和排序之间的关系是相反的，就像 davmac 说的那样。

比较下限的原因是您至少需要 nlogn 比较才能找到正确的顺序。有关更多详细信息，请参阅有关比较排序算法的此 wiki 页面。请注意，教授与插入无关（教授实际上并不假设任何插入）。

3 回答 3