-->
当前位置:首页 > 题库

回顾“最大值问题”(即找出数组中 $$n$$ 个元素中的最大值)的讨论,并行算法用了 CRCW 的同值规则做内存并发处理,以保证

Luz5年前 (2021-05-10)题库999
回顾“最大值问题”(即找出数组中 $$n$$ 个元素中的最大值)的讨论,并行算法用了 CRCW 的同值规则做内存并发处理,以保证 $$T(n) = O(1)$$ 的时间复杂度。事实上,我们还可以用任意值规则做内存并发处理,也能保持 $$O(1)$$ 时间复杂度。现在我们来考虑一种新的内存并发处理规则,叫 **C**oncurrent **R**ead **O**wner **W**rite (CROW),即每个内存单元有一个定义的“拥有者(Owner)”,只有这个“拥有者”可以向这个单元里写入。这样做就没有任何一种并行算法可以用 $$T(n) = O(1)$$ 的时间解决问题。 ~@[](2)

答案:TRUE