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

Question

下面的代码给出了 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);

}

Answer 1

不确定你在问什么，但你可以清楚地修改这段代码，并通过简单地摆脱重复递归(而不是递归地计算相同的东西两次)来赢得很多。

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

这样写可以让你编写一个 while 循环而不是递归。