第242页 | 算法技术手册 | 阅读 ‧ 电子书库

并行算法

一个计算过程可能会产生多个其他的计算过程用于同时处理一个问题的多个子实例。还拿上一小节离线算法的例子来说，如果在n个处理器上并行查找就有可能提高这n/2个顺序查找的性能，这样最坏情况的复杂度为O(n)。想要更深入了解并行算法，建议去读一下Berman和Paul（2004）年关于这个方面的著作。另外了解一些利用多核处理器并行机制的实际系统对也此也很有裨益，具体参见Armstrong的《Erlang编程：实现并发的利器》（2007）。