动态规划的POW函数计算

Question

我知道pow(base, power)是C语言的内置函数，复杂度为O(power)。我可以通过动态规划降低它的复杂度吗？

Answer 1

你可以在 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

Answer 2

如果您的输入参数是非负整数，那么您可以实现自己的 pow。

迭代，运行时间=O(n)：

unsigned long long pow(unsigned long long x,unsigned int n)
{
    unsigned long long res = 1;
    while (n--)
        res *= x;
    return res;
}

递归，运行时间=O(n)：

unsigned long long pow(unsigned long long x,unsigned int n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    return pow(x,n/2)*pow(x,n-n/2);
}

高效，运行时间 = O(log(n)):

unsigned long long pow(unsigned long long x,unsigned int n)
{
    unsigned long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res *= x;
        n >>= 1;
        x *= x;
    }
    return res;
}

动态规划的POW函数计算

Pow function calculation by dynamic programming

c++

dynamic-programming