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

Question

如何解决这种复发？ 归纳法是得到答案的唯一方法吗？如果是这样，你会如何猜测基本情况？

我的猜测是 O(logn) 但我不确定如何解决它。

Answer 1

递推关系为：

T(1) = c
T(n) = T(n - sqrt(n)) + T(sqrt(n)) + 1

我们可以写出几个条件：

n    T(n)
-    ----
1    c
2    c + c + 1 = 2c + 1
3    2c+1 + c + 1 = 3c + 2
4    2c+1 + 2c+1 + 1 = 4c + 3
5    3c+2 + 2c+1 + 1 = 5c + 4
6    4c+3 + 2c+1 + 1 = 6c + 5
…    …
9    6c+5 + 3c+2 + 1 = 9c + 8
…    …
k    kc + k - 1 = k(c + 1) - 1

在尝试了一些术语之后，它确实看起来是线性的。我们可以猜测 T(n) = k(c + 1) - 1 并尝试证明它。

基本情况：T(1) = c = 1(c + 1) - 1 = c + 1 - 1 = c。已验证

归纳假设：假设 T(n) = n(c + 1) - 1 对于所有 n 直至并包括 k

归纳步骤：显示 T(k+1) = (k+1)(c+1) - 1。从递归我们有 T(k+1) = T(k+1 - sqrt(k +1)) + T(sqrt(k+1)) + 1。根据归纳假设，这等于 (k+1 - sqrt(k+1))(c + 1) - 1 + sqrt(k+ 1)(c + 1) - 1 + 1。根据需要，简化为 (k+1)(c+1)-1-1+1 = (k + 1)(c + 1) - 1。

因此，T(n) = n(c + 1) - 1，结果是 T(n) = O(n)。