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)，这个问题就更有意义了) + 米

Answer 2

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

这意味着运行递归绝对不需要任何成本（甚至不需要 1 次操作），因此只要您的 n 在迭代中减少（确实如此，因为 n > n - sqrt(n)）。 ））你的递归实际上是免费的，

所以答案是O(1) PS，在现实生活中这是不可能的，因为你至少要做O(1)。递归的成本。