algorithm - 查找此算法的范围

我有以下算法：

  SUM-ARRAY(A,B,C):
     n = A.length
     grain-size = 1
     r = ceil(n/grain-size)
     for k = 0 to r-1:
          spawn ADD-S(A,B,C,k*grain-size+1, min((k+1)*grain-size,n))

     sync


  ADD-S(A,B,C,i,j):
  for k=i to j:
     C[k]=A[k]+B[k]

好的，我和我的小组讨论如下：
我们想找出这个算法的跨度，有些人认为它是θ（1）和其他θ（n）。
有什么帮助吗？

最佳答案

跨度，或者说关键路径长度，可以小于a a>作为“理论上在拥有无限多个处理器的计算机上执行工作的最快时间”。
在您的例子中，所有派生的迭代都是独立的，因此如果有足够的处理器，所有的迭代都可以同时执行。每一个迭代过程都需要大量的工作因此，跨度是θ（grain-size），如果以这种方式设置晶粒尺寸，它可以等于θ（1）或θ（n）甚至θ（sqrt（n））。对于粒度为1的代码，span是θ（1），即独立于迭代次数。

关于algorithm - 查找此算法的范围，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6095725/