关于一个递归的运行时间计算

Question

public static long pow(long x, int n){

    if(n == 0)

        return 1;

    if(n == 1)

        return x;

    if(n % 2 == 0)

        return pow(x, n/2) * pow(x, n/2);

    else

        return pow(x * x, n/2) * x;

}

    怎么计算这个方法的运行时间
    类似于O(NlagN)的表达形式

Answer 1

运算时间取决于运行程序的机器，同一个程序，不同计算机运行时间不同。
但是可以计算下递归的运行次数，很简单，定义一个全局变量，然后再在函数内+1
public static count = 0;
public static long pow(long x, int n){
count++;
...
}
执行程序，最后输出count就是这个递归函数调用的次数，调用次数可以反映你程序的算法复杂度。