ASh*_*lly 18 algorithm big-o partitioning stable-sort
我试图理解这篇论文:线性时间内稳定的最小空间划分.
似乎这个主张的一个关键部分是
算法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)写入到执行一个？
小智 5
我很想说这是不可能的。每当您要计算O（n log n）个信息量，但（1）无处可存放它（恒定空间），并且（2）无处可立即使用它（O（n）移动）时，发生了一些奇怪的事情可能涉及大量使用堆栈（虽然应该包括在空间分析中，但可能不包括在内）。
如果您将临时信息存储在仅一个整数之类的许多位数之内，则可能是有可能的。（所以实际上是O（1），但是理论上是O（log n）。）
基数排序不会完全做到这一点，因为您必须调用谓词才能创建数字，并且如果您不记住比较的可传递性，则将其称为O（n ^ 2）次。（但要记住，我认为每个项目需要O（log n）摊销空间。）
QED-缺乏想象力的证明:)