我在Coursera中学习分治算法，遇到了这种递归关系：T(n) = T(n-√n)+1
给出的答案是：O(√n)
我已经学会了主方法和递归树分析，但我不知道如何分析这种递归关系。
谢谢你的帮助。
最佳答案
在这一阶段，我们可以用二项式展开得到上界：
注意，RHS小于大的n的LHS，这意味着每次使用近似时，我们从参数减去较小的值到T，因此结果将是上界。
继续m迭代：
假设T(n)终止于n = 0（或某个常数，无所谓）
因此复杂性是O(m) = O(√n)。
编辑：上面的= 4√n是错误的，对不起-应该(2+5/√2)√n