T(n) = T(n - sqrt(n))

Question

有人知道如何解决这个递归问题吗？

大师定理在这里行不通。

Answer 1

这在O(1)中似乎是显而易见的，因为

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

通过归纳，你得到T(n) = T( epsilon )，其中epsilon接近于0。

如果T(n) = T(n - sqrt(n)) +m，则这个问题更有意义

Answer 2

你说得对，马斯特斯定理在这里不适用。如果仔细观察，您会发现递归的成本为零(右侧没有空闲元素：T(n) = T(m) + f(n)。

这意味着运行递归完全不需要任何成本(甚至一次操作都不需要)。所以，只要你的n在迭代过程中减少(因为是n > n - sqrt(n))，你的递归实际上是自由的。

所以答案是O(1)。附注:在现实生活中，这是不可能的，因为你至少会做O(1)作为递归的代价。