关注公众号【算法码上来】，每日算法干货马上就来！
题目链接
题目描述
实现 int sqrt(int n) 函数。
计算并返回 $n$ 的平方根，其中 $n$ 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例1
输入：
4
输出：
2示例2
输入：
8
输出：
2
解释：
8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。题解
为了更加通用，我们这里直接实现 double sqrt(double n) 函数。也就是求出 $\sqrt{n}$ 的精确值，然后取整就行了。
今天要教给大家的主要有三种方法：牛顿法、二分法和梯度下降法，速度上是依次下降的。
首先令 $\sqrt{n} = x$ ，也就是 $x^2 - n = 0$ ，也就是我们要求 $x^2 - n$ 的零点。
如果我们把 $x^2 - n$ 当作某个函数的导数，那么原函数就是 $f(x) = \frac{1}{3}x^3 - nx$ ，它的导数就是 $f’(x) = x^2 - n$ 。
现在问题很明朗了，要求 $\sqrt{n}$ 的值，等价于求 $f’(x) = 0$ 的根，等价于求 $f(x)$ 的极小值点（因为导数在非负数区间上零点唯一）。
牛顿法
求 $f’(x) = 0$ 的根可以采用牛顿法。
首先选取一个初值 $x_0$ ，然后在函数 $(x_0, f’(x_0))$ 处作切线，求出切线与 $x$ 轴交点 。接着将交点坐标作为新的 $x_0$ ，然后重复上面步骤，直到 $f’(x_0)$ 和 $0$ 差值小于某个阈值。
直接给出计算得到的更新公式吧，大家也可以自己通过切线方程推导一下：
$$
x_0 \leftarrow x_0 - \frac{f’(x_0)}{f’’(x_0)} = \frac{1}{2}(x_0+\frac{n}{x_0})
$$
还可以通过泰勒展开得到这个公式，这里就不详细阐述了。
梯度下降法
求 $f(x)$ 的极小值点可以采用梯度下降法。
首先选取一个初值 $x_0$ ，然后按照 $f(x_0)$ 的导数的逆方向更新 $x_0$ ，具体更新多少取决于你设置的学习率 $lr$ 。
更新公式就是：
$$
x_0 \leftarrow x_0 - lr \cdot f’(x_0) = x_0 - lr \cdot (x_0^2 - n)
$$
二分法
这就是很普通的二分方法了，因为 $f’(x)$ 在 $[0,\infty)$ 区间上是单调递增的，所以可以采用二分法求出零点，这里就不赘述了。
速度比较
我运行了一下从 $100$ 到 $10000$ 每 $100$ 个数开根号的结果，统计了一下三种方法需要的计算次数，如下图所示：
可以发现，牛顿法和二分法都是速度很快的，随着 $n$ 增大，需要的次数越来越多。但是梯度下降法的次数和学习率关系很大，学习率大了可能收敛次数变小，但是可能不收敛（左右振荡）。随着 $n$ 的增大，梯度下降法所需要的次数反而下降了，因为 $n$ 越大，函数越陡峭， $x_0$ 处的导数就越大，这样 $x_0$ 的更新幅度特别大。但是 $n$ 特别大了以后，梯度下降法需要的时间就非常长了，学习率不是很好设置了。而导数也已经超出了 int 范围，实现上也不是很方便。
具体实现
具体实现上这题有几个注意的点，因为这题只要求你返回取整结果，所以要特别当心浮点数误差。
而梯度下降法实现时，学习率不能太大，不然会产生振荡，此外还会导致 $x_0$ 更新幅度过大，直接变成负数，然后就陷入了死循环。
代码
c++
class Solution {
public:
int mySqrt(int x) {
long y = int(newtonSqrt(x)) + 1;
return y*y > x ? y-1 : y;
}
double newtonSqrt(double n) {
double x0 = n;
while (abs(x0*x0-n) >= 1e-6) {
x0 = 0.5*(n/x0+x0);
}
return x0;
}
double binarySqrt(double n) {
double l = 0, r = n;
while (r-l >= 1e-6) {
double m = (l+r)/2;
if (m*m < n) l = m;
else r = m;
}
return r;
}
// 超时
double gdSqrt(double n) {
double x0 = n;
while (abs(x0*x0-n) >= 1e-6) {
double lr = min(1e-3, 1e-1*x0/(x0*x0-n));
x0 = x0-lr*(x0*x0-n);
}
return x0;
}
};
