運行遞歸算法

對於上面的算法中，我只能計算出運行時間

if n==0:

是1和用於

運行時

rec_opt(n-1)

將是T（n-1）。但我不能找出運行時間

rec_opt(p[n])

爲什麼復發具有指數閉型，O（2^N ）

，此外，爲什麼這個算法將是O（n）。

2016-10-17 yashirq

rec_opt（P [N]）

對於遞歸調用rec_opt（P [N]），將有另一個遞歸樹將像rec_opt第（n-1）。由於p[n]可能是1 - n之間的任何值，我們可以假設它將起到rec_opt(n)的作用。

此外，爲什麼這個算法將是O（n）。

作爲memoization算法的算法的第二部分，它不會一次又一次計算相同的子問題。這就是爲什麼複雜度急劇下降到O(n)。

欲瞭解更多請致電dynamic programming。

2016-10-17 04:09:55 ruhul

現在我明白了rec_opt [n]。但是對於第一個算法的運行時間，即T（n）= 2T（n-1）+ c，不應該是O（n）？因爲n是T（n）中的最高項。 – yashirq

如果你正確理解了rec_opt（p [n]），那麼如果你用紙筆試試，複雜性將會很明顯。繪製一棵樹並計算節點的數量。對於第一個算法，您會看到您一次又一次地執行相同的任務。 – ruhul

回答