解決T（n-1）+ sqrt（n）的復發問題

Question

我希望我能以正確的方式解決這個問題。它要求解決復發：

T(n) = T(n-1) + sqrt(n)

到目前爲止，我已經研究並沒有能夠得到這一點：

T(n) = T(n-2) + (n-1) + sqrt(n) T(n) = T(n-3) + (n-2) + (n-1) + sqrt(n) T(n) = T(0) + 1 + 2 + ... + (n-2) + (n-1) + sqrt(n)

我無法理解的模式可能是什麼解決1 + 2 + ... + sqrt（n）

Answer 1

第二行已經是錯誤的。

如果T（N）= T（N - 1）+ SQRT（N），則T（N - 1）= T（N - 2）+ SQRT（N - 1），因此

Ť （n）= T（n-2）+ sqrt（n-1）+ sqrt（n）

T（n）= T ）+ SQRT（N）

T（N）= T（N - 4）+ SQRT（N - 3）+ SQRT（N - 2）+ SQRT（N - 1）+ SQRT（N）

等。

從1到n的平方根之和大約等於從1到n的sqrt（x）的積分。

Answer 2

從展開遞歸開始，您應該收到平方根的總和。平方根的總和是generalized harmonic number和你一個可以被近似：