algorithm - 我们如何进行并行秩排序以在 O(1) 时间内运行任意数量的处理器

Question

我知道并行秩排序的实现需要 O(log n) 时间和 O(n^2) 数量的处理器，如果我们使用并发写入，那么我们可以获得 O(1) 运行时间 O(n^2)处理器。有没有其他方法我们不使用并发读取并且运行时间为 O(1)。

Answer 1

基于比较的排序至少需要 O(n log n) 次比较。如果您不允许并发读取，那么在 O(1) 时间内对 n 个值进行排序，您最多可以读取（或操作）这些值 O(n) 次。所以我认为没有并发读取的 O(1) 并行排序必须非常奇特。事实上，考虑排序输出的任何单个值，例如第一个值，它可能是最低输入值。这取决于所有 n 个输入值。如果没有并发读取，我认为您可以将计算单个值的任何进程表示为在每个节点处具有有界度的树，并且在根处计算值。所花费的时间是树的深度，它必须至少为 O(log n)。