使用布尔数组排序数组

Question

A数组是Integer的数组，每个值只能出现一次。

B数组是Boolean的数组。

B[k] is True  when A[k] > A[k+1]

B[k] is False when A[k] < A[k+1]

是否可以编写一个使用复杂度小于bool的Tetta(n*logn)数组的sort Algorithm？

Answer 1

不，这是

不可能。让我们用contradiction

证明一下

事实：

在一般情况下，具有[[任意整数的A数组（为了使基数排序不可能而任意的数组）我们不能比O(N * log(N))。 假设问题中所述，O(N * log(N))和A数组的算法要比B好，比如说具有O(F(N))的时间复杂度；因此，具有任意的A数组，我们可以build具有B时间复杂度的相应O(N)。然后组合的复杂度是

O(N) + O(F(N)) = O(F(N))

因为我们必须循环遍历B数组，所以F(N)不能比O(N)好[[更好]（这就是为什么我们可以删除O(N)：O(N) + O(F(N)) = O(F(N))）的原因。到目前为止，到目前为止，我们已经成功地对

arbitrary

[A数组具有时间复杂性进行了排序

O(F(N)) < O(N * log(N)) 我们有矛盾，所以假设有算法是

错误

。