arrays - 是否可以在常数时间 O(1) 内使用 n 个 Common CREW 处理器在大小为 n 的排序数组中找到元素 x？

Question

给定一个 n 元素数组，如何使用常见的 CRCW 处理器在恒定时间内找到元素 x 在该数组中的位置？

假设 x 不在给定的数组中。甚至可以在常数时间 O(1) 中找到 x 在数组中的位置吗？

CREW 是一种可以并发读取但可以独占写入的处理器。

ps 这不是作业。

Answer 1

我在并行算法方面没有太多背景，但我认为您可以通过拥有 n 个内核并执行以下操作来做到这一点：

• 将结果设置为“未找到”
• 让 n 个处理器中的每一个执行以下操作，其中每个处理器都有一个不同的索引 k 分配给它：如果数组的第 k 个元素是 x，则将结果设置为 k。

一旦所有处理器完成它们的执行，结果变量，如果它被设置，将保存数组保存元素 k 的索引。每个处理器也只做 O(1) 的工作。

希望这会有所帮助，如果这种推理无效，请告诉我！