44. log(n)求a的n次方[power(a,n)]

【题目】

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

【分析】

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

C++ Code

1
2
3
4
5
6
7
8
9

double Power(double base, int exponent)
{
    ;
    ; i <= exponent; ++i)
        result *= base;

return result;
}

上述代码存在的问题：

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

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

改进之后代码如下：

【代码1】

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

bool g_bValid = true;

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

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

double Power(double base, int exponent)
{
    g_bValid = true;
    ))
    {
        )
        {
            g_bValid = false;
        }
        ;
    }

unsigned int absExponent = (unsigned int)exponent;
)
absExponent = (unsigned int)(-exponent);

double result = PowerWithUnsignedExponent(base, absExponent);
)
result = / 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

改进后代码如下：

【代码2】

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*
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)
)
        ;
    )
        return base;

);
result *= result;

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

【参考】

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

秒客网

44. log(n)求a的n次方[power(a,n)]

相关文章