网站备案在外地,推广方法和技巧,图片制作pdf,互动营销名词解释实现浮点类型的幂运算#xff0c;函数原型为: double pow(double x, int n) 在求解这个问题的时候是一个很挣扎的过程#xff0c;因为它不是报错而是一直提示你超出时间#xff0c;那么必须一次次的考虑怎样降低时间复杂度。 首先最直接的思路是下面这样的#xff0c;就跟直… 实现浮点类型的幂运算函数原型为: double pow(double x, int n) 在求解这个问题的时候是一个很挣扎的过程因为它不是报错而是一直提示你超出时间那么必须一次次的考虑怎样降低时间复杂度。 首先最直接的思路是下面这样的就跟直观的数学求解一样。 double pow(double x, int n)
{if(n0)return 1.0;if(n0)return 1.0/pow(x,-n);return x*pow(x,n-1);
} 但是会提示你超出时间这是可以理解的因为时间复杂度是O(n)。对于较大的n这是不可接受的。 其次 考虑到n个x相乘式子的对称关系可以对上述方法进行改进从而得到一种时间复杂度为O(logn)的方法递归关系可以表示为pow(x,n) pow(x,n/2)*pow(x,n-n/2)。 double pow(double x, int n)
{if(n0)return 1.0;if(n0)return 1.0/pow(x,-n);double half pow(x,n1);if(n%20)return half*half;elsereturn half*half*x;
} 这样时间复杂度降低了一个数量级但是仍然会超时。 最后网上搜答案查到下面的解决方案这根编程之美中求1的个数很类似。只不过加了一步数学幂转化为乘法即指数相加的过程。 描述如下 Consider the binary representation of n. For example, if it is 10001011, then x^n x^(128128) x^1 * x^2 * x^8 * x^128. Thus, we dont want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 i) to the result. Since (1 i) is a power of 2, x^(1(i1)) square(x^(1i)). The loop executes for a maximum of log(n) times. 该方法通过扫描n的二进制表示形式里不同位置上的1来计算x的幂次。 double my_pow(double x, int n)
{if(n0)return 1.0;if(n0)return 1.0 / pow(x,-n);double ans 1.0 ;for(; n0; x * x, n1){if(n10)ans * x;}return ans;
} 这里有一个问题就是当n等于INT_MIN时求绝对值之后会超出整数范围因为负数是比正数多一个的。在这里作为一个边界添加考虑即可。 if(n0) { if(nINT_MIN) return 1.0 / (pow(x,INT_MAX)*x); else return 1.0 / pow(x,-n); }
