在常量時間O（1）中使用n個常用CREW處理器，可以在大小爲n的有序數組中找到元素x？

Question

給定一個n元素數組，如何在常量時間內使用常見的CRCW處理器在該數組中找到元素x的位置？我們假設x不在給定的數組中。在恆定的時間O（1）中甚至有可能找到x的位置？

CREW是一種可以同時讀取但可以獨佔寫入的處理器。

p.s.這不是一項任務。

Answer 1

我沒有在並行算法多背景，但我認爲你可以有N個核，做如下做到這一點：

• 設置結果「未找到」
• 有各n個處理器執行以下操作，其中每個處理器具有分配給它的不同索引k：如果數組的第k個元素爲x，則將結果設置爲k。

一旦所有處理器完成其執行，結果變量（如果完全設置的話）將包含保存元素k的數組的索引。每個處理器也只做O（1）的工作。

希望這有助於，並讓我知道這個推理是無效的！