关于算法:每日一题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)