请大神比较这两种算法复杂度区别

我认为这两种空间复杂度和时间复杂度一样，为什么一个通过 一个不通过，求教大家

1.class Solution {
public:
    double myPow(double x, int n) {
        if (n < 0) return 1 / power(x, -n);
        return power(x, n);
    }
    double power(double x, int n) {
        if (n == 0) return 1;
        double half = power(x, n / 2);
        if (n % 2 == 0) return half * half;
        return x * half * half;
    }
};

2. double myPow(double x, int n) {
        if(x==0)return 0;
        if(n==0)return 1;
        if(n==1)return x;
        int m=n;
        if(n<0) m=-m;
        double a=x;
         vector<int>way;
        while(m!=1){
            if(m/2==0){m=m/2;way.push_back(1);}
            else {m=m-1;way.push_back(0);}
        }
        for(int i=0;i<way.size();i++){
            if(way[i]==1)x=x*x;
            else x=x*a;
        }
        if(n<0)return 1/x;
        else return x;
        
    }

第二个方法对吗？不应该是从后往前遍历vector？

我提个corner case
0的任何非0次方为0
但0的0次方为1

所以第二个函数里面 x等于0的判断跟n等于0的判断要换一下顺序

neoweb 发表于 2018-11-15 16:18
第二个方法对吗？不应该是从后往前遍历vector？

你说的对，但是我改过后还是现实memory limit exceeded, 不通过的例子是0.00001,272727

梦流星 发表于 2018-11-15 16:39
我提个corner case
0的任何非0次方为0
但0的0次方为1

0的0次方似乎数学不存在意义？

chenxianggre 发表于 2018/11/15 17:13:55


你说的对，但是我改过后还是现实memory limit exceeded, 不通过的例子是0.00001,272727

可能系统对heap卡的比较严 标准库的话overhead还是挺大的 可以试试bitvec

neoweb 发表于 2018-11-15 17:48
可能系统对heap卡的比较严 标准库的话overhead还是挺大的 可以试试bitvec

请教下heap bitvec是什么，不知道

chenxianggre 发表于 2018/11/15 17:50:54


请教下heap bitvec是什么，不知道

去搜一下stack和heap的区别

bitvec是cpp标准库提供的另一个collection 只能放二进制位 更省内存

但其实你都不需要用标准库 你完全可以根据n算出步数上界（2logn） new一个数组存储就够了

方法2中，while循环里的if应该是m%2，不是m/2