题解 | #求平方根#

NC32 求平方根

题意分析：

实现一个sqrt函数

题解一（二分法）：

该哪题可以转化为求满足 $k^2 \leq x$ 不等式的最大k值。k的取值范围可以确定是 $(0,x)$ 。可以通过二分法，寻找到k。

设置左端点l和右端点r，取其中间值得平方与x比较，如果等于x，返回mid；如果小于x，左端点更新为mid+1；如果过大于x，右端点更新为mid-1；

重复上面步骤。

代码实现：

int sqrt(int x) {
    int l = 0, r = x;
    int mid;
    while (l <= r) {
        mid = l + (r - l) / 2;
        //取中点作为比较
        if ((long long) mid * mid < x) {
          //如果中点的平方小于x，则更新left
            l = mid + 1;
        } else if ((long long) mid * mid > x) {
            //如果中点的平方大于x，则更新right
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return r;
}

时间复杂度： $O(lg x)$

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

题解二（牛顿迭代法）：

牛顿法（英语：Newton's method）又称为牛顿-拉弗森方法（英语：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数 $f(x)$ 的泰勒级数的前面几项来寻找方程 $f(x)$ 的根

求平方根问题可以转换为求 $f(x) = x^2-k=0$ 的近似解k。
过程如下：
假设r为 $f(x)=x^2-k=0$ 的根，我们选择一个 $x_0$ 作为r的初始近似值，过点 $(x_0,f(x_0))$ 做曲线 $y=f(x)$ 的切线L: $f(x_0)+f^{'}(x_0)(x-x_0)$ ,可求得曲线y与L的交点的x轴交点 $x_1 = x_0-\frac{f(x_0)}{f^{'}(x_0)}$ ,之后过点 $(x_1,f(x_1))$ 做曲线y的切线，重复上面步骤，会逐渐得到近似解。
通过上面的步骤，我们有了如下的递推公式 $x_{n+1} = x_n-\frac{f(x_n)}{f^{'}(x_n)}$ .
图片说明
参考wiki，下面给出一个c++实现：

int sqrt(int x) {
    if (x == 0) {
        return 0;
    }
    double x0 = x;
    while (true) {
        //迭代公式
        double xi = 0.5 * (x0 + x / x0);
        if (fabs(x0 - xi) < 1e-7) {
             //当达到指定的精度，则退出，返回结果
            break;
        }
        x0 = xi;
    }
    return int(x0);
}

时间复杂度： $O(lg \ x)$

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