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

簡化這種遞歸關係涉及的過程是什麼？如何找到遞歸關係T（N）= T（N/2）+ N^2

我能夠獲得這麼多：

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。過去，我陷入了一種解決這些問題的方式。

2014-03-25 Delps

這個問題似乎是題外話題，因爲它是關於數學而不是計算機編程。 –

我真的不明白你的觀點是1/2是否應該使用整數除法？如果這是您的真正目的，那麼爲什麼不總結所有的值，例如C（5）= C（2）+ 5^2 = C（1）+ 2^2 + 5^2 = C（0）+ 1^2 + 2^2 + 5^2 = 30？ – elias

那麼基本的想法是，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。

2014-03-26 01:18:53 elias

我在這裏回答了一個更一般的問題，使用相同的示例：http://stackoverflow.com/questions/22674053/simplifying-recurrence-relation-cn-cn-2-n2/22675310#22675310 – elias

回答