减少正数排序任务以证明 nlogn 复杂性

Question

事实证明，基于比较的排序具有复杂性 T(n)=nlogn。因此，如果我们有正整数数组（不是特定的整数，因此无法应用 counting 或 radix 排序）如何确定从 Sort 到 SortPositiveNumbers 的适当减少（对于示例）为了证明存在多项式和正确的变换并且 SortPositiveNumbers 也有 nlogn 的下界？

如有任何帮助，我们将不胜感激。

Answer 1

假设您可以对复杂度为 C' < nlogn 的正数进行排序。然后我可以通过将任意数组分成正数和负数 (O(N)) 将负数转换为正数 (O(N)) 对两个数组进行排序 (O(C')，乘以 2 来排序，但这并不重要复杂度），反转负数组 O(N) 并连接两个数组 (O(N))。因此，即使总体而言，复杂度也是 O(N + C')（即 O(N) 和 O(C') 之间的最大值）。这低于 nlogn ，您已证明这是对任意数组进行排序的最低复杂度。这是一个矛盾，因此最初的假设（我们所做的唯一假设）是错误的。那就是有一个复杂度小于 nlogn 的 co 算法来对正数进行排序。

Answer 2

我们可以使用以下伪代码将 Sort 简化为 SortPositiveNumbers：

Sort(A[1..n])
   B[1..n]
   p <- n+1
   s <- 0
   for k <- 1 to n
       if A[k] > 0
          p <- p-1
          B[p] <- A[k]
       else if A[k] < 0
          s <- s+1
          B[s] <- -A[k]

   SortPositiveNumbers(B[1...s])
   SortPositiveNumbers(B[p...n])

   for k <- 1 to s
       A[k] <- -B[s+1-k]
   for k <- s+1 to p-1
      A[k] <- 0
   for k <-p to n
      A[k] <- B[k]

这里的归约是线性的 (2n)，所以它是多项式的并且是正确的，因为它使用 SortPositiveNumbers 仅对 A 中的正数进行排序（负数转换为正数）最后再次归约将正数转换为负数，并且将它们添加到排序数组的所需索引中。

减少正数排序任务以证明 nlogn 复杂性

Reduction for positive number sorting task to prove nlogn complexity

sorting

algorithm

time-complexity

reduction