思路:假设我们要求的是整数c的平方根,那么平方根也就是$ x^2 - c = 0 $ 的解(因为曲线是$ y = x_2 - c $),假设此时我们在$(x_0, {x_0}^2-c)$,也就是曲线上的点
步骤如下:
- 过该点做切线,这个切线是不断逼近于$ y = x_2 - c $这个曲线与x轴的交点(也就是我们要求的),切线斜率求导可得为$ 2 * x_0 $,并且经过$(x_0, {x_0}^2-c)$,所以我们切线方程为 $ y = 2x_0*x-x_0^2-c $
- 切线与x轴交点的横坐标为$ \frac{x_0}{2} + \frac{c}{2x_0} $,下次我们就让$ x0 $ 移动到这个横坐标,然后开始下一次迭代,直到我们上一次迭代与下一次迭代的x的差距小于我们规定的值比如$ 1e-7 $,我们就认为迭代结束,然后返回结果
- 时间复杂度:O(log x),此方法是二次收敛的,相较于二分查找更快。
- 空间复杂度:O(1)。
不保留小数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| func SqrtII(x int) int {
c, x0 := float64(x), float64(x)
for { xi := x0/2 + c/(2*x0) if math.Abs(xi-x0) < 1e-7 { break } x0 = xi }
return int(x0) }
|
保留小数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| func SqrtToFloatII(x int) float64 { c, x0 := float64(x), float64(x)
for { xi := x0/2 + c/(2*x0) if math.Abs(xi-x0) < 1e-7 { break } x0 = xi } fmt.Println(fmt.Sprintf("%.4f", x0)) ret, _ := strconv.ParseFloat(fmt.Sprintf("%.4f", x0), 64) return ret }
|