并行化线性时间算法

Question

实际上,是否需要并行化线性时间算法？我的老师认为这不值得,但我不相信.

Answer 1

你的老师错了.单CPU算法的运行时复杂度(O(n),O(log n)等)与它是否将从并行化中受益无关.

将代码从使用1个CPU更改为使用K CPU将最多将运行时间除以K因子.由于无法凭空创造CPU,K实际上是一个常数.因此,运行时复杂性不受并行化的影响.您所希望做的就是不断改进因素.

这并不是说它不值得做 - 在某些情况下,两倍的改进是非常有益的.此外,在数千个CPU的大规模并行系统中,该常数变得非常大.

Answer 2

肯定是的。显卡提供并行性，从 CPU 切换到 GPU 上的并行计算可以节省大量时间。并行执行时，线性时间算法可以实现巨大的加速。请参阅GPGPU和“应用程序”部分，或谷歌搜索“显卡计算”。

虽然你没有问，但理论上的答案也是肯定的，对于可以“有效并行化”的问题（可以在给定处理器多项式数量的对数时间内解决）和“P-complete”的问题，存在一个复杂度等级 NC可以在多项式时间内解决但怀疑不能在 NC 中解决的问题。（就像有P问题和NP完全问题，而NP完全问题被怀疑不在P中）

Answer 3

考虑到足够大的输入，这是值得的。总是。

示例：在无序“列表”中查找最大数字的简单算法只会遍历该列表。这将花费订单时间O(n)来查找记录。

如果您有 100 或 1000 条记录，这没问题。

如果您有十亿条记录怎么办？您将列表拆分为多个 CPU，每个 CPU 找到一个最大值，然后您就有一个新的较小列表可供使用。您可以再次拆分它 => 并行，而且速度更快。我相信O(log(n))如果你有效地分割和减少，并且有n 个 CPU 的话。

要点是：如果你的输入足够大，O(n)就不再足够好。根据需要完成的任务，与您想要的相比，O(n) 可能会增长到太多秒、分钟、小时。

注意：当我说O(n)或O(log(n))上面时，我指的是完成搜索所需的时间。即不是所有CPU 执行的“总工作”。通常，并行化算法会在一定程度上增加 CPU 完成的总工作量。