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)-1-1+1= (k + 1)(c + 1) -1。

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