1.函数

随便看的题目

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，$x^n$ ）。

pow(x,n)用法

// pow valarray example
#include <iostream>     // std::cout
#include <cstddef>      // std::size_t
#include <cmath>        // std::pow
#include <valarray>     // std::valarray, std::pow

using namespace std;

int main ()
{
    valarray<double> val (5);//变量数组
    valarray<double> results;//结果

    /* 初始化 */
    for (int i=0; i<5; ++i) 
        val[i]=i+1;
    cout << "val:";
    for (size_t i=0; i<val.size(); ++i) 
        cout << ' ' << val[i];
    cout << '\n';
	//val: 1 2 3 4 5
    
    results = pow (val,val);
    cout << "val^val:";
    for (size_t i=0; i<results.size(); ++i) 
        cout << ' ' << results[i];
    cout << '\n';
    // val^val: 1 4 27 256 3125

    results = pow (val,2.0);
    cout << "val^2:";
    for (size_t i=0; i<results.size(); ++i) 
        cout << ' ' << results[i];
    cout << '\n';
    // val^2: 1 4 9 16 25

    results = std::pow (2.0,val);
    cout << "2^val:";
    for (size_t i=0; i<results.size(); ++i) 
        cout << ' ' << results[i];
    cout << '\n';
    // 2^val: 2 4 8 16 32

    return 0;
}

暴力解法——连乘法

class Solution {
public:
    double myPow(double x, int n) {
        if(n < 0){
            n = -n;
            x = 1/x;
        }
        double ans = 1.0;
        for(int i = 0;i < N;++i)
            ans *= x;
        return ans;
    }
};

时间复杂度：$O(n)$

空间复杂度：$O(n)$

调库函数

class Solution {
public:
    double myPow(double x, int n) {
        return pow(x,n);
    }
};

题解快速幂

分治法

$$x^{64}\rightarrow x^{32}\rightarrow x^{16}\rightarrow x^8\rightarrow x^4 \rightarrow x^2\rightarrow x\\ x^{77}\rightarrow x^{38}\rightarrow x^{19}\rightarrow x^{9}\rightarrow x^4 \rightarrow x^2 \rightarrow x$$

• 边界条件 n==0 ，返回1
• 当前步计算 $y= x^{\lfloor \frac{n}{2} \rfloor}$ ，即上一步的平方
  • 若是偶数，则进入下一层
  • 若是奇数，y*=x，进入下一层

注意：

若n是负数，则最后返回倒数

1. 递归

class Solution {
public:
    double mul(double x,int n){
        if(n == 0)
            return 1.0;
        double y = 1.0;
        if(n & 1){//n是奇数
            y = x;
        }
        return y * pow(mul(x,n/2),2);
    }

    double myPow(double x, int n) { 
        return n >=0 ? mul(x,n) : 1/mul(x,n);
    }
};

时间复杂度：$O(logn)$ 递归层数

空间复杂度：$O(logn)$