【每日算法Day 67】经典面试题:手动开根号,你知道几种方法?

题目链接

LeetCode 69. x 的平方根[1]

题目描述

实现 int sqrt(int n) 函数。

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

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

示例1

        输入:
4
输出:
2

      

示例2

        输入:
8
输出:
2
解释:
8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

      

题解

为了更加通用,我们这里直接实现 double sqrt(double n) 函数。也就是求出 的精确值,然后取整就行了。

今天要教给大家的主要有三种方法:牛顿法二分法梯度下降法,速度上是依次下降的。

首先令 ,也就是 ,也就是我们要求 的零点。

如果我们把 当作某个函数的导数,那么原函数就是 ,它的导数就是

现在问题很明朗了,要求 的值,等价于求 的根,等价于求 f(x) 的极小值点(因为导数在非负数区间上零点唯一)。

牛顿法

的根可以采用牛顿法。

首先选取一个初值 x_0 ,然后在函数 (x_0, f'(x_0)) 处作切线,求出切线与 x 轴交点 。接着将交点坐标作为新的 x_0 ,然后重复上面步骤,直到 f'(x_0)0 差值小于某个阈值。

直接给出计算得到的更新公式吧,大家也可以自己通过切线方程推导一下:

还可以通过泰勒展开得到这个公式,这里就不详细阐述了。

梯度下降法

f(x) 的极小值点可以采用梯度下降法。

首先选取一个初值 x_0 ,然后按照 f(x_0) 的导数的逆方向更新 x_0 ,具体更新多少取决于你设置的学习率 lr

更新公式就是:

二分法

这就是很普通的二分方法了,因为 f'(x) 区间上是单调递增的,所以可以采用二分法求出零点,这里就不赘述了。

速度比较

我运行了一下从 10010000100 个数开根号的结果,统计了一下三种方法需要的计算次数,如下图所示:

v2-22b6304ab99a49563c064997ad75c8aa_b.jpg


可以发现,牛顿法和二分法都是速度很快的,随着 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;
    }
};

      

参考资料

[1]

LeetCode 69. x 的平方根: leetcode-cn.com/problem

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

点赞 评论 收藏
分享
你是来当牛马的吧:行了,照片拍完了,让大家都回工位吧
点赞 评论 收藏
分享
真java练习生:他的回答真的是太糟糕了,就像隔壁苏珊婶婶做的苹果派一样
点赞 评论 收藏
分享
11-06 09:58
西京学院 Java
有友友了解菜鸟怎么样呀,比较想去杭州,会裁应届嘛
努力的飞舞:菜鸟只给p4?
投递菜鸟集团等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务