java - 确定程序运行时间？

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

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)

我是不是走对了路，我有点糊涂了，你还要说明印刷线的事吗？

最佳答案

分析是正确的，直到最后，解是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
您也可以在wolfram alpha