algorithm - 另一个内部递归调用的递归关系

Question

我正在尝试分析这段代码的成本:

static int funct1(int x) {
     if (x<=1) return x;
     return funct1(funct1(x/2)) + 1;
}

我如何解决递归关系 T(n)=T(T(n/2))+1？

Answer 1

您的分析不正确。 T(n) = T(f(n/2)) + T(n/2) + 1(你错过了 T(n/2) 但程序应该先计算T(n/2)，然后运行T(f(n/2))。它不是 T(T(n/2))。

现在尝试将f(n) 视为函数funct1 的值。假设 n = 2^k, f(2^k) = f(f(2^{k-1})) + 1 = f(f(2^{k-2 }) + 1) + 1 = ... = f(f(f(...f(1) + 1..)+1)+1) + 1。 f(1) = 1, f(2) = 2, f(3) = 2, f(4) = 3, f(8) = f(f(4)) + 1 = f(3) + 1 = 3, f(16) = f(f(8 )) + 1 = f(3) + 1 = 3，f(32) = f(f(16)) + 1 = f(3) + 1 = 3。如您所见，它对所有值 2^k 和 f(2^k) = 3 重复。

因此，T(n) = T(3) + T(n/2) + 1 = O(log n)。