首页 > 代码库 > 44. log(n)求a的n次方

44. log(n)求a的n次方

2024-07-05 11:45:57   225人阅读

 题目：实现函数double Power(double base, int exponent)，求base的exponent次方，不需要考虑溢出。

分析：这是一道看起来很简单的问题，很容易写出如下的代码：

double Power(double base, int exponent)
{
      double result = 1.0;
      for(int i = 1; i <= exponent; ++i)
            result *= base;
 
      return result;
}

上述代码存在的问题：

（1） 由于输入的exponent是个int型的数值，因此可能为正数，也可能是负数，上述代码只考虑了exponent为正数的情况。

（2） 底数为0，指数为负数，则输入非法。

改进之后代码如下：

bool g_bValid = true;

bool Equal(double num1,double num2)
{
    double gap = 0.00000001;
    if (num1-num2>-gap && num1-num2<gap)
        return true;
    return false;
}

double PowerWithUnsignedExponent(double base,unsigned int exponent)
{// T(n) = O(n)
    double result = 1.0;
    for (int i=0;i<exponent;++i)
        result *= base;
    return result;
}

double Power(double base,int exponent)
{
    g_bValid = true;
    if(Equal(base,0.0))
    {
        if (exponent < 0)
        {
            g_bValid = false;
        }
        return 0.0;
    }

    unsigned int absExponent = (unsigned int)exponent;
    if (exponent<0)
        absExponent = (unsigned int)(-exponent);

    double result = PowerWithUnsignedExponent(base,absExponent);
    if (exponent<0)
        result = 1.0/ result;

    return result;
}

其时间复杂度为O(n)，如何进一步改进？

我们可以用如下公式求a的n次方，其时间复杂度为O(lgn)：

n is even: a^n = a^(n/2)*a^(n/2)

n is odd: a^n = a^((n-1)/2)*a^((n-1)/2) * a

改进后代码如下：

/*
n is even: a^n = a^(n/2)*a^(n/2)
n is odd: a^n = a^((n-1)/2)*a^((n-1)/2) * a
*/
double PowerWithUnsignedExponent2(double base,unsigned int exponent)
{// T(n) = O(lgn)
    if (exponent==0)
        return 1;
    else if (exponent==1)
        return base;

    double result = PowerWithUnsignedExponent2(base,exponent>>2);
    result *=result;

    if (exponent& 0x1)
    {// exponent is odd
        result*=base;
    }
    return result;
}

参考：

http://zhedahht.blog.163.com/blog/static/254111742009101563242535/

 


联系
我们