如何找到遞歸關係T（N）= T（N/2）+ N^2

Question

簡化這種遞歸關係涉及的過程是什麼？

我能夠獲得這麼多：

T(n) = T(n/2) + n^2 
T(n) = T(n/4) + (n/2)^2 +n^2 
T(n) = T(n/8) + (n/4)^2 + (n/2)^2 + n^2 

我明白這將終止當n = 1，因爲1/2 = 0; C（0）= 0。 過去，我陷入了一種解決這些問題的方式。

Answer 1

那麼基本的想法是，C(N)和C(N/2)應該是一個表達式相同的形式。由於它們的區別是N的簡單功能，所以無限的總和應該流入您的腦海，對此C(N)-C(N/2)變得可伸縮。總和的每個項應該是N/2^k（對於k=0, 1, ...）作爲其參數的給定函數。

因此C(N) = N^2 + (N/2)^2 + (N/4)^2 + (N/8)^2 + ...完成這項工作，並且可以使用幾何序列的身份進一步評估它，如C(N)=4/3*N^2。