leetcode-69|leetcode-69 X的平方根 leetcode-69X的平方根

问题描述实现int sqrt(int x)函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:

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

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

前言本题是一道常见的面试题，面试官一般会要求面试者在不使用
函数的情况下，得到 x 的平方根的整数部分。一般的思路会有以下几种：

通过其它的数学函数代替平方根函数得到精确结果，取整数部分作为答案；
通过数学方法得到近似结果，直接作为答案。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
来源：力扣（LeetCode）
方法一：（暴力法）袖珍计算器算法「袖珍计算器算法」是一种用指数函数和对数函数代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。
我们将写成幂的形式，再使用自然对数进行换底，即可得到

【leetcode-69|leetcode-69 X的平方根】这样我们就可以得到的值了。
注意：由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x = 2147395600x=2147395600 时，
的计算结果与正确值 4634046340 相差，这样在对结果取整数部分时，会得到 4633946339 这个错误的结果。
因此在得到结果的整数部分 ans后，我们应当找出 ans 与ans + 1中哪一个是真正的答案。

# 袖珍计算器法 def mySqrt1(self, x): if x == 0: return 0 res = int(math.exp(0.5*math.log(x))) # 考虑误差 return res+1 if (res+1)**2 <= x else res

复杂度分析时间复杂度：，由于内置的 exp 函数与 log 函数一般都很快，我们在这里将其复杂度视为。
空间复杂度：)。
方法二：二分查找由于x平方根的整数部分 ans 是满足的最大k 值，因此我们可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案ans 后，也就不需要再去尝试 ans+1 了。

# 二分查找 def mySqrt2(self, x): if x == 0: return 0 l, r, res = 0, x, -1while l <= r: mid = (l+r)/2 if mid**2 <= x: res = mid l = mid + 1 else: r = mid - 1 return res

复杂度分析时间复杂度：，即为二分查找需要的次数。
空间复杂度：。
方法三：牛顿迭代法思路
牛顿迭代法是一种可以用来快速求解函数零点的方法。
为了叙述方便，我们用 C 表示待求出平方根的那个整数。显然，C 的平方根就是函数

的零点。
牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个
?作为初始值，在每一步的迭代中，我们找到函数图像上的点，过该点作一条斜率为该点导数的直线，与横轴的交点记为。相较于而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。下图给出了从开始迭代两次，得到和的过程。

文章图片
image.png
算法我们选择作为初始值。
在每一步迭代中，我们通过当前的交点，找到函数图像上的点，作一条斜率为的直线，直线的方程为：

与横轴的交点为方程的解，即为新的迭代结果 :

在进行 k 次迭代后，的值与真实的零点足够接近，即可作为答案。
细节

为什么选择作为初始值？
- 因为有两个零点和。如果我们取的初始值较小，可能会迭代到这个零点，而我们希望找到的是这个零点。因此选择作为初始值，每次迭代均有，零点在其左侧，所以我们一定会迭代到这个零点。
迭代到何时才算结束？
- 每一次迭代后，我们都会距离零点更进一步，所以当相邻两次迭代得到的交点非常接近时，我们就可以断定，此时的结果已经足够我们得到答案了。一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数，其中一般可以取
  或。
如何通过迭代得到的近似零点得出最终的答案？

由于在上是凸函数（convex function）且恒大于等于零，那么只要我们选取的初始值大于等于，每次迭代得到的结果都会恒大于等于。因此只要选择地足够小，最终的结果只会稍稍大于真正的零点
。在题目给出的 32 位整数范围内，不会出现下面的情况：

真正的零点为，其中 n 是一个正整数，而我们迭代得到的结果为。在对结果保留整数部分后得到 n，但正确的结果为 n - 1。

#牛顿迭代 #f(x) = x^2+C,这里容易引起歧义，输入的x变量为C，输出的结果为x def mySqrt3(self, x): if x == 0: return 0C,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)

复杂度分析时间复杂度：，此方法是二次收敛的，相较于二分查找更快。
空间复杂度：。