如何為 T(n) = 4T(n-1) 2. 繪制遞回樹，其中 n>1 且 T(1) = 2。通常最后有 n，但在這種情況下沒有。
uj5u.com熱心網友回復：
給定的遞回關系有一個常數項，這導致了一個非常簡單的遞回樹：
_______________2______________
/ / \ \
__2__ __2__ __2__ __2__
/ | | \ / | | \ / | | \ / | | \
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
... ... ... ...
樹的層數由回圈項確定： ?? ??分解為 ?? ???1， ?? ???2，... 直到 ?? 1，所以樹有 ?? 層。
首先分別對每個級別求和。
如果我們從上到下對層進行編號，頂層編號為 0，底層為 ???1，則層 ?? 有 4 個??節點。
因此，所有節點的數量是 ∑ ??=0..???1 4 ??。這表示幾何級數的第一項，因此我們在整個樹中計算 (4 ?? ?1)/3 個節點。
由于每個節點的值為 2，因此總值為 2(4 ?? ?1)/3
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/375100.html
上一篇：如何遞回地重復陣列中的元素n次？