求浮点数x的平方根, 以及求pow(x, n)

2020-08-14 | 阅读：次

实现求浮点数x的平方根函数, 要求误差精度小于 epision = 1e-10 ,其函数原型为：

double sqrt(double x, double eps);

1.二分法

时间复杂度 二分法的时间复杂度为 O(log(x))

double sqrt(double x, double eps = 1e-10) { 
    assert(x >= 0);
    double l = 0, r = x >= 1 ? x : 1, mid;
    while (fabs(l * l - x) > eps) {
        mid = l + (r - l) / 2;
        if (mid < x / mid) l = mid;
        else r = mid;
    }
    return l;
}

2.牛顿迭代法

分析： 设 sqrt(x) = t, 则问题相当于求 t * t - x = 0 的解，令 f(t) = t*t - x

首先取x0,如果x0 不是解，做一个经过 (x0, f(x0)) 点的切线，与 x 轴交点为 x1 .

同样地，如果 x1 不是解，做一个经过 (x1, f(x1)) 点的切线，与 x 轴交点为 x2. 依此类推，直到满足条件。

double sqrt(double x, double eps = 1e-10) {
    assert(x >= 0);
    double res = x;
    while (fabs(res * res - x) > eps) {
        res = (res + x / res) / 2;
    }
    return res;
}
}

3.梯度下降法

分析： 将 sqrt(x) 看作机器学习中的优化问题，可以使用梯度下降法求解。
令 f(t) = t * t - x, 则我们可以求 L(t, x) = (x - t * t) * (x - t * t)的最小值，对 L(t, x) 求导可得： d L(t, x)/ dt = 4 * t * (t * t - x) .

实现代码:

double sqrt(double x, double eps = 1e-10) {
    assert(x >= 0);
    double lr = 1e-3, delta = 1.0, res = x >= 1 ? x : 1;
    while (fabs(delta) > eps) {
        delta = 4 * res * (res * res - x);
        res -= lr * delta;
    }
    return res;
}

x的平方根

leetcode 69

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

    int mySqrt(int x) {
        long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return r;
    }

求 pow(double x, int n).

方法一： 快速幂法 + 递归

double pow(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1 / x;
    double mid = pow(x, n / 2), rest = pow(x, n % 2);
    retrun rest * mid * mid;
}

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

空间复杂度：O(log(n)) 递归的层数。

方法二： 快速幂法 + 迭代

double pow(double x, int n) {
    double res = 1.0;
    for (int i = n; i; i /= 2) {
        if (i & 1) res *= x;
        x *= x;
    }
    return n >= 0 ? res : 1 / res;
}

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

空间复杂度：O(1)

king-yyf