18

我试图理解这篇论文：Stable minimum space partitioning in linear time。

该主张的一个关键部分似乎是

算法 B在 O(nlog 2 n)时间和恒定额外空间内稳定地排序大小为n的位数组，但只进行O(n)次移动。

但是，该论文没有描述该算法，而仅引用了我无法访问的另一篇论文。我可以找到几种在时间范围内进行排序的方法，但是我很难找到一种既能保证 O(N) 移动又不需要超过恒定空间的方法。

这个算法B是什么？换句话说，给定

boolean Predicate(Item* a);  //returns result of testing *a for some condition

是否有一个函数可以使用PredicateB(Item* a, size_t N);作为排序键对 Predicate进行稳定排序，对 Predicate 的调用少于 nlog 2 n，并且只对a执行 O(N) 写入操作？

4

3 回答 3

5

我很想说这是不可能的。每当您计算 O(n log n) 的信息量但 (1) 无处存放它（恒定空间），以及 (2) 无处可立即使用它（O(n) 移动）时，就会有一些奇怪的事情发生on，可能涉及大量使用堆栈（可能不包括在空间分析中，尽管应该包括在内）。

如果您将临时信息存储在一个整数的许多位中，或者类似松鼠的东西，这可能是可能的。（所以实际上是 O(1)，但理论上是 O(log n)。）

基数排序不会完全做到这一点，因为您必须调用谓词来创建数字，如果您不记住比较的传递性，那么您将调用它 O(n^2) 次。（但要记住，我认为每个项目需要 O(log n) 摊销空间。）

QED - 缺乏想象力的证明:)

于 2011-03-29T21:11:42.083 回答
2

这是我到目前为止所拥有的。循环排序的一种版本，它使用位数组来保存分区测试的结果并即时计算目的地。它使用 N 次比较、< N 次交换和恰好 2N位分配的存储执行稳定的二进制分区。 

int getDest(int i, BitArray p, int nz)
{   bool b=BitArrayGet(p,i);
    int below = BitArrayCount1sBelow(p,i);  //1s below
    return (b)?(nz+below):i-below;
}

int BinaryCycleSort(Item* a, int n, BitArray p)
{
   int i, numZeros = n-BitArrayCount1sBelow(p,n);
   BitArray final = BitArrayNew(n);
   for (i=0;i<numZeros;i++)
      if (!BitArrayGet(final,i))
      {  int dest= GetDest(i,p,numZeros);
         while (dest!=i)                
         {  SwapItem(a+i,a+dest); 
            BitArraySet(final,dest);
            dest = getDest(dest,p,numZeros);
         }
         BitArraySet(final,dest);
      }
   return numZeros;
}

int BinaryPartition(Item* a, int n, Predicate pPred)
{ 
   int i;
   BitArray p = BitArrayNew(n);
   for (i=0;i<n;i++)
      if (pPred(a+i)) BitArraySet(p,i);
   return BinaryCycleSort(a,n,p);
}

使用这些助手：

typedef uint32_t BitStore;
typedef BitStore* BitArray;
BitArray BitArrayNew(int N); //returns array of N bits, all cleared
void BitArraySet(BitArray ba, int i); //sets ba[i] to 1
bool BitArrayGet(BitArray ba, int i); //returns ba[i]
int BitArrayCount1sBelow(BitArray ba, int i) //counts 1s in ba[0..i)

显然这不是恒定的空间。但我认为这可能被用作最终目标的基石。使用固定大小的 B 位 BitArray 可以将整个数组划分为 N/B 个块。有没有办法在执行稳定合并时重用这些相同的位？

于 2011-03-30T07:52:15.370 回答
0

不是RadixSort吗？

O(kN)

于 2011-03-28T22:24:12.160 回答