復發關係樹方法

我目前在解決我們的一些復發問題方面存在問題，並且因爲我有很多關於它即將推出的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

復發關係樹方法

回答

相關問題