题目描述

实现 int sqrt(int x) 函数。

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

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

样例

示例 1:
输入: 4
输出: 2

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

算法1

(二分查找) $O(logn)$

在1到x之间二分查找答案即可。

时间复杂度

二分查找时间复杂度为$O(n)$

参考文献

C++ 代码

class Solution {
public:
    int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        int l = 1, r = x;

        while (l <= r){
            int mid = l + (r - l) / 2;
            if (mid > x / mid) r = mid - 1;
            else l = mid + 1;
        }

        return r;
    }
};

算法2

(牛顿法) $O(logn?)$

牛顿法迭代，
$a_k = a_{k - 1} - f(a_{k - 1})/ f’(a_{k - 1})$
$f(a) = a ^ 2 - x$
所以$a_k = (x / a_{k-1} + a_{k-1}) / 2$

时间复杂度

应该比二分法更快一点？

参考文献

C++ 代码

class Solution {
public:
    int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        double a = x;

        while (abs(a * a -x) > 1e-2){
            a = (x / a + a) / 2;
        }

        return a;
    }
};

算法3

(梯度下降) $O(?)$

最小化代价函数$J(a) = (a^2 - x) ^ 2$(貌似不是凸函数hh)
$a$的初始值设为$x$,每次迭代$a = a - \alpha * 4a * (a ^ 2-x)$
学习率$\alpha$调不好会不收敛，代码供玩耍hh

class Solution {
public:
    int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        double a = x;
        double alpha = a / 10000000;

        while (abs(a * a - x) > 1e-2){
            a -= alpha * 4 * a * (a * a - x);
        }

        return a;
    }
};