快速幂求x的n次方

缺乏、安全感 2022-07-16 09:55 261阅读 0赞

# 问题 #

O(logn)的时间复杂度求x的n次方，x为自然数，n为整数？

# 举例解析 #

如果 power=5 为奇数，result保存当前的多余的一个4，并在返回结果时一并与结果相乘。  
2^10 = (2\*2) \* (2\*2) \* (2\*2) \* (2\*2) \* (2\*2)= 4 ^5 = 4^4 \* 4

4^4 = (4\*4) \* (4\*4) = 16 ^ 2

16^2 = 16 \* 16 = 256

如果 power=1 时，结果返回base=256  
256^1 = 256

# 数学证明 #

求x^y?
    y使用二进制数表示：
    
    y = 2^y0 + 2^y1 + 2^y2 + 2^y3 + ... + 2^yn
    
    
    x^y = x^(2^y0 + 2^y1 + 2^y2 + 2^y3 + ... + 2^yn)
        = x^(2^y0) * x^(2^y1) * x^(2^y2) * x^(2^y3) * ... * x^(2^yn-1) * x^(2^yn)
    
    证明：x^(2^yn) = (x^(2^yn-1))^(2^yn-1), yn = 2 * yn-1 ?
    
         x^(2^yn) = x^(2^(2 *yn-1))
                  = x^(2^yn-1 * 2^yn-1)
                  = (x^(2^yn-1))^(2^yn-1)

# 递归版 #

int fast_pow(int base, int power) {
        if (base == 0) return 0;
        if (power == 0) return 1;
        if (power == 1) return base;
    
        if (power%2 == 1)
            return base*fast_pow(base*base, power/2);
        return fast_pow(base*base, power/2);
    }

# 非递归版 #

int fast_pow2(int base, int power) {
        if (base == 0) return 0;
        if (power == 0) return 1;
        if (power == 1) return base;
    
        int result = 1; // 在power为奇数时，保存当前的base值(value)
        int value = base;
        for (; power > 1; value*= value, power/=2) {
            if (power%2 == 1) result *= value;
        }
        return result * value;
    }

# 时空复杂度 #

f(n)函数为fast_power算法的执行的基本操作的执行次数
    f(1) = 0
    f(n) = f(n/2)+1
         = f(n/2^2) + 1 + 1
         ...
         = f(n/2^k) + k
    当n/2^k = 1，k=logn，f(n) = logn
    则fast_power算法的时间复杂度为O(logn)
    空间复杂度为O(1)

# 参考 #

[Fast Power Algorithm: C/C++ and Python Code][Fast Power Algorithm_ C_C_ and Python Code]  
[快速冪 Exponentiation by squaring | 黃鈺程][Exponentiation by squaring _]  
[Fast Power][]

[Fast Power Algorithm_ C_C_ and Python Code]: http://www.rookieslab.com/2013/05/fast-power-algorithm-cc-and-python-code.html
[Exponentiation by squaring _]: https://henrybear327.gitbooks.io/gitbook_tutorial/content/Algorithm/fast_pow/index.html
[Fast Power]: http://www.cnblogs.com/yuzhangcmu/p/4174781.html