如何证明并行算法的上下界？
如何证明并行算法的上下界？
提问于 2018-01-08 01:55:50
假设有一个Fibonacci算法：
我们被要求证明这个算法的上界/下界。
我该如何继续？
更新
因此，我将解释我自己做了什么，并指出我被困在哪里了。
我不知道为什么，但我决定在这里使用递归关系，看看我可以在哪里得到最终结果。但我怀疑我的工作的原因是，上下限是对算法在资源方面的“无限”的识别。
因此，并行算法具有：
功(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老实说，我不知道这是否有意义。
给出了一个形式化的解决方案：
但我不太理解上面所采取的步骤
回答 1
Stack Overflow用户
发布于 2018-01-08 07:39:02
我想说的是，处理器几乎是无关紧要的，因为递归是一棵树，而这棵树的节点数量是指数级的。这些节点表示在每个步骤中必须完成的合并。因此，即使处理器的数量是无限的，这也无助于解决这种递归问题，因为它们只能独立地计算最后一行中的某些东西，即W(1)和W(0)。
我只是在评论中看到了提供的样本解决方案，并部分解释了:这里有一些进一步的“洞察力”：想法是扩大递归并寻找一种收集因素的方法。在这里，他们以应用不等式的方式收集2: W(n-1)+W(n-2) >= 2W(n-2)。所以现在你有W(n)>= 2W(n-2)。多少次我们减去2直到我们有W(0)在右边？n/2次。然后你得到了Omega(2^(n/2))的下界。您可以使用或多或少相同的方法来显示上限。
顺便说一句，这些界限并不紧：Related Post
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48139987
复制相关文章
相似问题
腾讯云开发者
