整数的幂计算（三种方法）最快O(logn)

旧城等待， 2023-08-17 17:43 8阅读 0赞

# 整数的幂计算 #

> github: [https://github.com/Sean16SYSU/Algorithms4N][https_github.com_Sean16SYSU_Algorithms4N]

**算法1：** 一般来说的常见的计算 x n x^n xn的方式，就是逐步乘上x，这样一共需要 O ( n ) 次 O(n)次 O(n)次的乘法  
**算法2：** 但如果 x 4 x^4 x4的话，其实我们只需要计算一次 x 2 x^2 x2，再用两个 x 2 x^2 x2相乘就好了。这样的话，算法复杂度就被降低到了 O ( l o g n ) O(log n) O(logn) 。如果不是偶数的话，也可以通过提取出一个偶数来得到对应的结果。**用递归的方式很容易就解决上面描述的算法。**

**算法3：** 但是，指数部分的是可以很容易用二进制表示出来的。这样我们就通过获取对应的二进制位就来实现递推实现(且由于不存在递归调用，一定程度上可以提高速度)。

## 算法1: ##

#include <iostream>
    using namespace std;
    
    double power(double x, unsigned int n) { 
    	double y = 1;
    	for (int i = 0; i < n; ++i) {  y *= x; }
    	return y;
    }
    
    int main() { 
    	double x;
    	unsigned int n;
    	cin >> x >> n;
    	cout << power(x, n) << endl;
    	system("pause");
    }

## 算法2 ##

#include <iostream>
    using namespace std;
    
    double power(double x, unsigned int n)
    { 
        double y;
        if (n == 0)
            y = 1;
        else
        { 
            y = power(x, n / 2);
            y = y * y;
            if (n % 2 == 1)
                y *= x;
        }
        return y;
    }
    
    int main()
    { 
        double x;
        unsigned int n;
        cin >> x >> n;
        cout << power(x, n) << endl;
        system("pause");
    }

## 算法3 ##

#include <iostream>
    using namespace std;
    
    double power(double x, unsigned int n)
    { 
        double y = 1;
        while (n != 0)
        { 
            if (n % 2)
                y *= x;
            x *= x;
            n /= 2;
        }
        return y;
    }
    
    int main()
    { 
        double x;
        unsigned int n;
        cin >> x >> n;
        cout << power(x, n) << endl;
        system("pause");
    }

[https_github.com_Sean16SYSU_Algorithms4N]: https://github.com/Sean16SYSU/Algorithms4N