复发关系树方法

我目前在解决我们的一些复发问题方面存在问题，并且因为我有很多关于它即将推出的midterms，所以我真的可以使用一些帮助，也许可以解释它是如何工作的。复发关系树方法

所以我基本上已经解决河内

TOWER_OF_HANOI (n, FirstRod, SecondRod, ThirdRod) 
    if n == 1 
      move disk from FirstRod to ThirdRod 
    else 
      TOWER_OF_HANOI(n-1, FirstRod, ThirdRod, SecondRod) 
       move disk from FirstRod to ThirdRod 
       TOWER_OF_HANOI(n-1, SecondRod, FirstRod, ThirdRod)

塔伪代码并提供了我知道如何写的关系（其中，老实说，我不知道我这样做...）应该为T （n）= 2T（n-1）+Ɵ（n），对吗？我有点理解如何用分数子问题来生成一棵树，但即使如此，我还是不完全理解这个过程，它会给你最终的解决方案，Ɵ（n）或Ɵ（n log n）或者什么都不是。

感谢您的任何帮助，这将不胜感激。

来源

2016-10-13 GiantDwarf

假设时间复杂度为T（n）时，它被认为是：T（N）= T（N-1）+ T（N-1）+ 1 = 2T（N-1） + 1.为什么“+1”而不是“+ n”？由于“将磁盘从FirstRod移动到ThirdRod”只需要一次移动。
对于T（N）= 2T（N-1）+ 1，它的递归树将正好是这样的： https://www.quora.com/What-is-the-complexity-of-T-n-2T-n-1-+-C（你可能会发现，像整齐）C是一个常数;这意味着每次操作的成本。在河内塔的情况下，C = 1。
计算每个级别的成本总和，在这种情况下你会很容易地发现总成本将是2^n-1，这是指数昂贵）。因此，这个递归方程的答案是Ɵ（2^n）。

来源

2016-10-13 01:35:55

复发关系树方法

回答

相关问题