并行化已经是线性时间算法

Question

在实践中，已经是线性时间复杂度的算法是否需要并行化呢？我的老师认为这没有必要，但我不太相信。

- minhle_r7

---

这将取决于算法通常要处理的元素数量，这些元素之间的依赖关系，当然还要看是否有并行处理器可用以获得一些加速。 - codeling

我认为这完全是错误的思维方式。如果它太慢了（无论速度有多快），并且可以并行化，那么它就值得。不管时间复杂度等等如何。在现实世界中，实时性很重要。如果它不太慢，那么就没关系了。即使它实际上是一个指数时间算法。 - harold

Answer 1

你的老师是错误的。单CPU算法的运行时间复杂度（O(n), O(log n)，等等）与是否能从并行化中受益无关。

将代码从使用1个CPU改为使用K个CPU最多只能将运行时间减少K倍。由于你不能随意从空气中创建CPU，所以K实际上是一个常数。因此，并行化不会影响运行时复杂度。你所能做的只是获得一个常数因子的改进。

这并不是说没有价值——在某些情况下，两倍的改进是非常有益的。此外，在成千上万个CPU的大规模并行系统中，这个常数变得相当大。

- mbeckish

---

+1，但是如果你只是指单个系统，那么K就是一个常数。如果你谈论的是算法在一系列不同系统上的性能，K就会变成一个变量。 - SmacL

将代码从使用1个CPU更改为使用K个CPU，最多只能将运行时间缩短K倍，这并不一定是真的。虽然在实际问题中很少出现，但存在超线性加速的可能性（例如，请参见http://en.wikipedia.org/wiki/Speedup）。 - codeling

@nyarlathotep - 很有趣，但我希望他们在那个部分提供参考资料。他们大多数的论点（缓存等）似乎导致了更大的常数因子增加，而不是从O(n)到O(log n)的变化。请参阅阿姆达尔定律- http://en.wikipedia.org/wiki/Amdahl%27s_law。 - mbeckish

@mbeckish，您当然是正确的，但原始问题涉及算法，因此我倾向于从算法复杂度的角度考虑答案，其中K是一个变量。 - SmacL

是的，加速可能会超线性增长，考虑使用剪枝进行搜索空间遍历（约束满足问题DFS求解器（优化问题）+剪枝+刮胡子）。使用多个核心/线程，您可以从一个线程中修剪/刮去其他线程的搜索空间... - malejpavouk

Answer 2

肯定是的。图形卡提供并行性，从CPU切换到GPU上的并行计算可以节省大量时间。线性时间算法在并行执行时可以获得巨大的加速。请参见GPGPU和“应用程序”部分，或Google搜索“图形卡计算”。

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

- sdcvvc

Answer 3

我也不同意你的老师。我的观点是，在MapReduce上运行的许多算法都是线性时间算法。

例如，索引、遍历许多html页面（例如维基百科中的所有页面）并查找特定单词的算法是输入线性的算法。然而，如果没有并行处理，你无法真正运行它。

- Guy

Answer 4

如果输入足够大，那么它是值得的。总是如此。

例如：一个朴素的算法来查找无序列表中最大的数字只需遍历列表。这将花费O(n)的时间来查找记录。

如果你有100个或1000个记录，这还可以接受。

如果你有10亿条记录呢？你可以将列表分成多个CPU，每个CPU找到一个最大值，然后你就有了一个新的较小列表来处理。你可以再次分割 => 并行处理，速度更快。我相信如果你有效地分割和减少，并且拥有n个CPU，那么它的时间复杂度应该是O(log(n))。

重点是：如果你的输入足够大，O(n)已经不够好了。根据需要完成的任务，O(n)可能会增长到比你想要的时间多出许多秒、分钟或小时。

注意：当我在上面提到 O(n) 或 O(log(n)) 时，我指的是完成搜索所需的时间，而不是所有 CPU 执行的“总工作量”。通常情况下，并行化算法会增加 CPU 执行的总工作量。

- ArjunShankar

---

如果问题需要检查每个元素，则无法获得比O(n)更好的结果。然而，通过并行化可以使检查同时进行，从而加快速度。 - Don Roby

@ArjunShankar，我认为说当n是输入元素数量时时间复杂度为O(log(n))是错误的，除非你保证有n个CPU。更好的做法是说如果你有m个CPU，你的性能将接近于O(n/m)。 - SmacL

@ArjunShankar - 我们可能只是彼此误解了。在计算并行算法的运行时复杂度时，线程/ CPU的数量（m）和输入大小（n）通常被视为独立变量。在这种情况下，您不能使用并行化将O（n）算法更改为O（log n）。实现这一点的唯一方法是将m视为n的函数。例如，如果m = n / log（n），则O（n / m）等同于O（log n）。 - mbeckish

@ArjunShankar - 我的观点是，在谈论运行时复杂度时，说“使用具有>= n/2处理器的机器”是没有意义的。人们在确定运行时复杂度时不考虑处理器数量作为输入大小的函数。 - mbeckish

@ArjunShankar，如果你被允许使用n个CPU，并且共享内存读取没有开销，那么你理论上的最佳log(n)似乎对于这个简单的问题而言相当慢。假设每个CPU查看当前最高值，将其与其输入数组中的每个值进行比较，并在更大时更新最高值，则运行时间接近O(1)。我坚持认为是O(n/m)，其中n和m是独立变量。对于任何非平凡算法，我认为变量的数量要大得多，运行时间复杂度的表达式也是如此。 - SmacL

Answer 5

假设在单核、单 CPU、单机环境下，且任务是 CPU 绑定的情况下，你的老师是正确的。（尽管可以争论，在这种情况下，即使你运行多个线程，它们也不是真正并行运行的，只是给人以并行运行的假象）

然而，现在的单核系统已经很少见了，甚至许多智能手机都开始采用多核技术，因此在实践中，你可能会从并行化中受益。我说“可能”，是因为如果任务很小，线程创建的成本将会比收益更高，同样还有上下文切换的开销。如果没有明智地进行操作，使一个操作并行化实际上可能会使其变得更慢。

- Davy8