关于算法:每日一题x-的平方根

69. x 的平方根

关键词：袖珍计算器算法、二分查找、牛顿迭代

题目起源：69. x 的平方根 – 力扣（Leetcode）

题目形容

 T 袖珍计算器算法
 T 二分查找
 T 牛顿迭代

给你一个非负整数 x，计算并返回 x 的 算术平方根。

因为返回类型是整数，后果只保留 整数局部 ，小数局部将被 舍去。

留神：不容许应用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。

输出：x = 4
输入：2

输出：x = 8
输入：2

数据范畴 
0 <= x <= 2^31 - 1

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数和对数函数代替平方根函数的办法。

依据√x=e^1/2lnx，从而失去√x 的值。因为浮点数的值是不准确的，所以后果可能存在差一谬误，须要增加额定判断。

int mySqrt(int x) {if (!x)return x;
    int res = exp(0.5 * log(x));
    return (long long) (res + 1) * (res + 1) <= x ? res + 1 : res;
}

工夫复杂度：O(1)

空间复杂度：O(1)

二分查找

x 的平方根的整数局部 res 必然是满足 k ²≤x 的最大 k。若有 k1 不满足 k ²≤x，则小于 k1 的 k 也不满足 k ²≤x，故 k 具备枯燥性，因而可采纳二分来求解。k 的下界为 0，上界无妨定为 x。

int mySqrt(int x) {if (x < 2)return x;
    int l = 1, r = x, mid;
    while (l < r) {
        // r-l+ 1 可能会溢出
        mid = l + ((r - l + 1) >> 1);
        if (mid > x / mid)r = mid - 1;
        else l = mid;
    }
    return l;
}

工夫复杂度：O(log(n))

空间复杂度：O(1)

牛顿迭代

牛顿迭代法能够用来疾速求解函数零点。

令 C 示意待求出平方根的那个整数，显然 C 的平方根就是函数 y =f(x)=x²- C 的零点。

任取一点 x _i作为初始值，找到函数上的点 (xi, f(xi))，过该点做函数的切线，交 x 轴于 x _i+1，x_i+1 相较于 x _i间隔零点更近，屡次迭代后，就能失去一个间隔零点十分近的交点。

点 (xi, f(xi)) 处函数的切线的斜率为 2x_i，故直线切线方程为 y _i=2x_ix-(x_i²+C)，得与 x 轴的交点 x _i+1=(x_i+C/x_i)/2。

因为 y =f(x)=x²- C 有两个零点，为了失去正的那个零点，x_i的初始值应该取 C。最初的后果会稍稍大于正零点。

int mySqrt(int x) {if (x < 2)return x;
    double C = x, x1 = 0, x2 = x;
    while (fabs(x2 - x1) > 1e-7) {
        x1 = x2;
        x2 = (x2 + C / x2) / 2;
    }
    return int(x2);
}

工夫复杂度：O(log(n))。此办法是二次收敛的，相较于二分查找更快。

空间复杂度：O(1)