解决一个复发的关系T（N）= T（N-√N）+1

Question

我学习的分而治之在Coursera的算法，我也遇到过这样的复发关系：

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

答案给出的是：

O(√n)

我已经学会了掌握方法和复发树分析，但我不知道如何分析这种复发的关系。
感谢您的帮助。

Answer 1

我们可以通过使用二项展开式获得在此阶段的上界：

注意，RHS比LHS为大n越小，这意味着每个时间我们应用近似值，我们从参数中减去一个较小的值到T，因此结果将是一个上限。

继续m迭代：

假设T(n)终止于n = 0（或一些常数，无所谓）

，因此复杂性是O(m) = O(√n)。

---

编辑：= 4√n上述错了，对不起 - 本来应该是(2+5/√2)√n