java递归计算幂时，我不理解方法的输出

Question

当我尝试递归计算2^8时，我不知道这个方法会被使用31次

这个方法计算O（logN）复杂度的幂吗

当我运行它时，输出是：

0
1
2
3
4
5
...
29
30
2^8 is: 256

密码

private static int power(int x, int y)
{
    System.out.println(step++);

    if (y == 0)
        return 1;

    return power(x, y/2) * power(x, y/2);
}

Answer 1

不，它不是O（logN），它是O（NlogN）

在每次迭代中，您创建的问题只有问题大小的一半（这很好），但您创建的是两个问题

你应该这么做，而不是

 return power(x, y/2) * power(x, y/2);

这个

 int power = power(x, y/2);
 return power * power;