Arj*_*kar 7 algorithm complexity-theory
这个问题来自于另一个问题的讨论: 并行化线性时间算法.这不是功课.
您将获得一组N数字,以及一台带有P处理器和共享CREW内存的计算机(并发读取,独占写入内存).
找到数组中最大数字的最快算法的最严格 上界是什么？[显然,也是:算法本身是什么？]
我指的是所执行的工作总量[ 永远不会低于O(N)].
我想是的O(N/P') + O(Log2(P')),在哪里P'=min{N,P}.P'处理器搜索max的N/P'每个元素,其次是Log2并行完成成对合并.第一次P'/2合并由偶数编号处理器完成,接下来是'P'/ 4' - 处理器在可被8整除的位置,然后是16,依此类推.
P'引入编辑以涵盖处理器节点明显多于需要搜索的元素的情况.
Cook,Dwork和Reischuk表明,任何用于查找最多n个元素的CREW算法都必须在Omega(lg n)时间内运行,即使处理器数量不限且内存不受限制.如果我没记错的话,他们的论文中会出现一个匹配上限的算法:
Stephen Cook,Cynthia Dwork和RüdigerReischuk.没有同时写入的并行随机访问机器的上限和下限时间.SIAM Journal on Computing,15(1):87-97,1986.