java - (c ^ k)的大O表示法

以下代码给我一个O（n）。如何编写时间复杂度为O（c ^ k）的for循环？

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);

}

最佳答案

不确定您要问的是什么，但是您可以通过简单地消除重复的递归（而不是递归地两次计算同一件事）来清楚地修改此代码并赢得很多利益。

if (y%2 == 0) {
    int res = power(x, y/2);
    return res * res;
}

用这种方式编写它将允许您编写while循环而不是递归。

关于java - (c ^ k)的大O表示法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17259996/