java - 计算程序运行时间？

Question

我正在尝试计算拆分程序的运行时间，

void splitX(int x) {
     if (x<=1) {return x;};
     splitX(n/2);
     System.out.println("splitting in progress");
     splitX(n/2);
     splitX(n/2);
     splitX(n/2);
}

我对此很陌生，这是迄今为止所做的；

T(n) = 4T(n/2)
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = O(log n)

我在正确的轨道上吗，我有点困惑，你还需要考虑打印线吗？

Answer 1

分析到最后都是正确的，解决方案是T(n) = O(n^2)

请注意 4^kT(n/2^k) != O(log n)自 4^k不是常数。
看看分析:

T(n) = 4T(n/2) = 
     = 4^2T(n/2^2)
     = 4^3T(n/2^3)
     = 4^kT(n/2^k)
     = 4^log(n)*T(1) =
     = 4^log(n) * 1 =
     = (2^log(n))^2 =
     = n^2
     = O(n^2)

为了正式证明它:我们使用 induction
基地:T(1) = 1 = 1^2
假设T(n) = n^2对于每个 k <= n
T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2

因此归纳假设为真且T(n) = n^2

您也可以在 wolfram alpha 上查看此结果