我知道 pow(base, power)
是 C 中的一个内置函数,复杂度为 O(power)。我可以通过动态规划降低它的复杂度吗?
最佳答案
你可以在 O(logn) 中计算它
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
详见 Here
关于c++ - 动态规划的POW函数计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31024503/