给定一个 n 元素数组，如何在常数时间内使用常见的 CRCW 处理器找到该数组中元素 x 的位置？
假设 x 不在给定的数组中。是否有可能在常数时间 O(1) 内找到数组中 x 的位置？
CREW 是一种可以并发读取但可以独占写入的处理器。
附注这不是作业。
最佳答案
我在并行算法方面没有太多背景，但我认为您可以通过拥有 n 个内核并执行以下操作来做到这一点:
- 将结果设置为“未找到”
- 让 n 个处理器中的每一个执行以下操作，其中每个处理器都分配有不同的索引 k:如果数组的第 k 个元素是 x，则将结果设置为 k。
一旦所有的处理器完成它们的执行，结果变量，如果它被设置的话，将保存一个包含元素 k 的数组的索引。每个处理器也只做 O(1) 的工作。
希望这对您有所帮助，如果此推理无效，请告诉我!
关于arrays - 能否在常数时间 O(1) 内使用 n 个 Common CREW 处理器在大小为 n 的排序数组中找到元素 x？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19739245/