complexity-theory - 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

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

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

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