2. X 的平方根

1. 牛顿迭代法

这种算法的原理很简单，我们仅仅是不断用 (x,f(x)) 的切线来逼近方程 x^2-a=y(y为0)的根。根号 a 实际上就是 x^2-a=0 的一个正实根，这个函数的导数是 2x。也就是说，函数上任一点 (x,f(x)) 处的切线斜率是 2x。那么，x-f(x)/(2x) 就是一个比 x 更接近的近似值。代入 f(x)=x^2-a 得到 x-(x^2-a)/(2x)，也就是 (x+a/x)/2

const mySqrt = function mySqrt(x) {
  // 数学方法 牛顿迭代 公式 r = ( r + x / r ) / 2
  let r = x
  while (r ** 2 > x){
      r = Math.floor((r + x / r) / 2);
  } 
  return r
};

复杂度分析

时间复杂度: O (F (n) logn), F(n) = f(n) / f’(n) = mid / x . 牛顿法每次迭代后的精度都为前一次的两倍.
空间复杂度: O (1)