2

假设一个斐波那契算法：

在此处输入图像描述

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

我该如何进行？

更新

所以我会解释我自己做了什么，并说明我被困在哪里。

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

所以，并行算法有：

功(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

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

给出了正式的解决方案： 在此处输入图像描述

但我不太明白上面采取的步骤

4

1 回答 1

0

我会说处理器几乎没有关系，因为递归是一棵树，而且这棵树有指数级的节点。这些节点代表必须在每个步骤中完成的合并。因此，即使处理器的数量是无限的，它也无助于解决这种重复，因为它们只能在最后一行独立计算一些东西，即 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)) 下限。您可以使用或多或少相同的方法来显示上限。

顺便说一句，这些界限并不严格：相关文章

于 2018-01-07T23:39:01.777 回答