我想了解本文：稳定的最小空间分区 在线性时间。

I'm trying to understand this paper: Stable minimum space partitioning in linear time.

看来，索赔的关键部分是，

It seems that a critical part of the claim is that

算法B 各种稳定了一下数组大小的 N 的中    O（n日志 2 N）的时间和不断的额外的空间，但这样只能的 O（N）的动作。

Algorithm B sorts stably a bit-array of size n in O(nlog2n) time and constant extra space, but makes only O(n) moves.

不过，本文不介绍算法，而只是引用，我没有机会到其他文件。我能找到几种方法可以做到在时间范围内的排序，但我无法找到一个保证O（N）的动作，而不需要也超过一定的空间。

However, the paper doesn't describe the algorithm, but only references another paper which I don't have access to. I can find several ways to do the sort within the time bounds, but I'm having trouble finding one that guarantees O(N) moves without also requiring more than constant space.

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

What is this Algorithm B? In other words, given

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

有一个函数 B（项目*一，为size_t N）; 其稳定排序的在的使用的 predicate 作为排序键比n日志 2 n次的调用，以predicate，并且只执行O（N）写的在的？

is there a function B(Item* a, size_t N); which stably sorts a using Predicate as the sort key with fewer than nlog2n calls to Predicate, and performs only O(N) writes to a?

推荐答案

我很想说，这是不可能的。任何时候你要计算为O（n log n）的信息量，但有（1）无处藏匿它（恒定的空间），和（2）无处可立即使用它（O（n）的动作），有什么奇怪的打算上，可能涉及大量使用堆栈（其可以不包括在该空间分析，虽然它应该是）。

I'm tempted to say that it isn't possible. Anytime you're computing O(n log n) amount of information but have (1) nowhere to stash it (constant space), and (2) nowhere to immediately use it (O(n) moves), there is something weird going on, possibly involving heavy use of the stack (which may not be included in the space analysis, although it should be).

如果您商店里面只是一个整数，或一些疯狂的像许多位临时信息这是可能的。 （所以，O（1）的做法，但为O（log理论上N）。）

It might be possible if you store temporary information inside many bits of just one integer, or something squirrelly like that. (So O(1) in practice, but O(log n) in theory.)

基数排序也不太做，因为你必须调用predicate创建数字，如果你不memoize的比较的传递，那么你叫它为O（n ^ 2 ）次。 （但要memoize的需要每个项目的O（log n）的摊销空间，我想。）

Radix sorting wouldn't quite do it because you'd have to call the predicate to create the digits, and if you don't memoize the transitivity of comparison then you'll call it O(n^2) times. (But to memoize it takes O(log n) amortized space per item, I think.)

QED - 证明是缺乏想象力：）

QED - Proof by lack of imagination :)