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

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).

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

Recurence relation of recursive call inside another

algorithm

recursion

complexity-theory

time-complexity