数学计算

# 68-x的平方根-简单

实现int sqrt(int x)函数。
计算并返回 x 的平方根，其中 x 是非负整数。

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

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

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

本题有多种解法。典型的如二分法、牛顿法等。

# 方法一：二分法

假设的平方根的整数部分为，则可得，根据二分法可以不断逼近值。
每次只需比较中间元素与的大小关系。代码如下：

def mySqrt(self, x: int) -> int:
    l, r, ans = 0, x, -1
    while l <= r:
        mid = (l + r) // 2      # l+(r-l)//2 避免溢出
        if mid * mid <= x:
            ans = mid
            l = mid + 1
        else:
            r = mid - 1
    return ans

• 时间复杂度：
• 空间复杂度：

# 方法二：牛顿迭代法

牛顿迭代法是一种可以用来快速求解函数零点的方法。

• 原理
  假设用整数 代表待求出平方根的平方，令 。
  牛顿迭代法本质上借助于泰勒级数，从一个初始值开始不断逼近函数零点。若取 作为初始值，其在函数对应的点为。过该点作一条切线交轴于点 ，切线斜率为 。经过多次迭代后，我们就可以得到距离零点非常近的交点，将其近似为 的平方根。如下图所示。

• 算法步骤
  假设选择 作为初始值。
  一般情况下，设在每次迭代时切线与 轴交点为 ，则函数上的点为 ，切线斜率为 ，则切线的方程为：

  求出该方程的解即为切线与轴的交点，即新的迭代点：
  经过若干次迭代，直到 的值与零点的差值小于给定的误差范围，即可作为答案。

• 问题

  • 为什么选择 作为初始值？
    因为函数 有两个零点 和 ，如果选择的初始值较小，可能迭代到 这个零点。
  • 迭代到何时才算结束？
    一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 ，如 可取 。

• 代码

def mySqrt(self, x: int) -> int:
    if x == 0:
        return 0
    
    C, x0 = float(x), float(x)
    while True:
        xi = 0.5 * (x0 + C / x0)
        if abs(x0 - xi) < 1e-7:
            break
        x0 = xi
    
    return int(x0)

• 时间复杂度：
  相较于二分法更快。具体复杂度分析暂时不懂，有知道的大神可以解释下。
• 空间复杂度：

# 方法三：梯度下降法

梯度下降法是一种可以求解函数极小值的优化算法。其核心就是使参数朝着函数下降最快的方向进行更新。 而函数下降最快的方向，可以理解为函数的梯度的负方向。

• 原理
  假设是一个关于变量的函数，为了求得的极小值，可以利用导数(二元函数为梯度)进行迭代。
  递推关系：
  

  其中表示当前值，表示新的值，是前进的步长。
  过程如图所示：
  
  

• 算法步骤
  定义损失函数。
  

  
  其中表示迭代过程的变量。损失函数使用平方是为了保持函数的连续性并使其可以求导。
  可以看到，当时，我们可以求得的极小值，也即是和差距最小时候，此时可以将作为的平方根的近似解或精确解。
  根据递推表达式，可以推出：
  

• 代码

def mySqrt(self, x: int) -> int:
    if x == 0:
        return 0
    x0, alpha = 1, 0.0001
    max_num = 1000
    der_threshold = 0.00001
    for i in range(max_num):
        der = -4 * x0 * (x - x0 ** 2)
        if abs(der) <= der_threshold:
            return int(x0+1)
        x -= alpha * der
    return int(x0+1)

• 时间复杂度：
• 空间复杂度：

备注：方法三在具体计算时可能造成溢出或计算不准确，取决于步长alpha，der_threshold和max_num。