algorithm - 如何证明并行算法的上限/下限？

Question

假设一个斐波那契算法:

我们被要求证明这个算法的上限/下限。

我该如何继续？

更新

因此，我将解释我自己所做的事情并展示我遇到的问题。

我不知道为什么，但我决定在这里使用递推关系，看看在哪里可以得到我的最终结果。但我之所以怀疑我的工作，是因为上限/下限是算法在资源方面“无限”的标识。

因此，并行算法有:

功(n) = W(n - 1) + W(n - 2) + Θ(1)

在这一点上，我决定使用递归关系——不知道——

Work(n) = [W(n - 1) + W(n - 2) + Θ(1)] + W(n - 2) + Θ(1)
        = W(n - 2) + W(n - 2) + 2Θ(1)
        = 2W(n - 2) + 2
        = Stuck here

老实说，我不知道这是否有意义。

给出了正式的解决方案:

但是上面的步骤我不是很明白

Answer 1

我想说处理器几乎没有关系，因为递归是一棵树，而这棵树的节点数呈指数级增长。这些节点代表必须在每个步骤中完成的合并。因此，即使处理器的数量是无限的，也无助于解决这种递归问题，因为它们只能在最后一行独立计算某些东西，即 W(1) 和 W(0)。

我刚刚在评论中看到提供了示例解决方案并进行了部分解释:这里有一些进一步的“见解”:想法是扩大循环并寻找收集因素的方法。在这里，他们以应用不等式的方式收集 2:W(n-1)+W(n-2) >= 2 W(n-2)。所以现在你有 W(n)>= 2 W(n-2)。我们多久减去 2 一次，直到右侧有 W(0)？ n/2 次。然后你最终得到 Omega(2^(n/2)) 下界。您可以使用大致相同的方法来显示上限。

作为一个小旁注，这些界限并不严格:Related Post