时间戳

首页 > 解决方案 > 串行算法和并行算法有什么区别？

algorithm - 串行算法和并行算法有什么区别？

问题描述

我确实听说过串行和并行处理以及编程。但是我的导师问了这个问题，什么是串行和并行算法。我在谷歌上搜索它，但没有找到任何简单而有用的内容。

有人可以轻松地说一下吗？

标签： algorithm

解决方案

阅读维基百科。

并行算法只是允许并行处理的算法。

例如，看一下Merge Sort，它的正常递归实现已经是并行算法（因此归并排序是并行的尴尬）。请注意，对于 n 个线程，归并排序的时间复杂度将是 O(log n) 而不是 O(n log n)。其他示例包括快速傅立叶变换和可在此处找到的完整列表。

串行算法是不是并行算法的算法（即它不允许并行处理）

例如，如果你想找到一个数组的最大元素，你可以这样做：

a = [2, 4, 3, 2]
ans = -Infinity
For i From 0 To Len(a) - 1
  ans = Max(ans, a[i])
Return ans

编译器/解释器无法并行运行它，因为它是迭代的。它的本质是顺序运行。但是，您可以以不同的方式实现它以使其成为并行算法，例如：

Def Solve(arr)
  if Len(arr)=0
    Return -infinity
  if Len(arr)=1
    Return arr[0]
  Divide arr into two part left=arr[0..len(a)/2] and right=arr[len(a)/2+1..len(a)-1]
  Return Max(Solve(left), Solve(right))
a = [2, 4, 3, 2]
Return Solve(a)

有了这个实现，Solve(left)并且Solve(right)可以同时运行没有任何问题，所以它是一个并行算法。请注意，对于 n 个线程，此实现的时间复杂度将为 O(log n) 而不是前面示例中的 O(n)。

然而，并不是每个算法都可以轻松并行化。事实上，有一类叫做P-complete的问题很难有效地并行化。（例如电路值问题）

推荐阅读