哪一种算法能在只有O(N)移动的情况下进行稳定的二进制分割？
我试图理解这篇论文：在线性时间内稳定的最小空间分割。
看来，一个关键部分是
算法B稳定地在 O（nlog 2 n）时间和恒定的额外空间中对大小为n的位数组进行排序，但只进行O（n）运算。
然而，这篇论文并没有描述算法，只是引用了另一篇我无法访问的论文。我可以找到几种方法在时间范围内进行排序，但是我很难找到一种能够保证O（N）移动而不需要超过固定空间的方法。
这个算法B是什么？换句话说，给出
boolean Predicate(Item* a); //returns result of testing *a for some condition
是有一个功能B(Item* a, size_t N);，其稳定地排序一个使用谓词如少于NLOG排序键2个 n次呼叫到谓词，只有O（N）写入到执行一个？
回答 2
Stack Overflow用户
发布于 2018-03-29 11:01:41
我很想说这是不可能的。任何时候你计算O（n log n）的信息量，但有（1）无处存储（恒定空间）和（2）无处立即使用它（O（n）移动），有一些奇怪的事情可能涉及大量使用堆栈（可能不包括在空间分析中，尽管它应该是）。
如果你将临时信息存储在只有一个整数的许多位中，或者是像这样的松鼠般的东西，那么这可能是可能的。（所以O（1）在实践中，但理论上是O（log n）。）
基数排序并不完全是因为你必须调用谓词来创建数字，如果你不记忆比较的传递性，那么你会称它为O（n ^ 2）次。
Stack Overflow用户
发布于 2018-03-29 11:18:00
这是迄今为止我所拥有的。循环排序的一个版本，它使用一个位数组来保存分区测试的结果并即时计算目的地。它执行一个稳定的二进制分区，包含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块。有没有办法在执行稳定合并时重新使用这些相同的位？
https://stackoverflow.com/questions/-100007853
复制相似问题