- 前言
- 一、牛顿-拉弗森法（Newton-Raphson Method）
- 二、二分查找法（Binary Search）
- 1.算法原理
- 2.Python实现
- 三、两种算法的效率比较
- 总结
前言
这是一道经典的面试题：自己编写函数实现根号2（根号n）的求解。排除显然答案：
from math import sqrt print(sqrt(2))一、牛顿-拉弗森法（Newton-Raphson Method）
这个方法被认为同时被艾萨克·牛顿和约瑟夫·拉弗森提出，所以名为牛顿-拉弗森法。
结论：如果存在一个k是多项式p的根的有效近似，那么k - p(k) / p’(k)就是一个更有效的近似值。其中p’是p的一次导数。
求解根号n可以转化为求多项式x ^ 2 - n的根的问题，该多项式的一次导数是2x. 因此，如果当前的猜测是k, 那么可以选择k - (k ^ 2 - n) / 2k 作为下一个猜测值，直到误差（k ^ 2 - n）的绝对值小于给定的值epsilon. 这种方法称为逐次逼近。
Python实现：
# 利用牛顿-拉弗森法寻找平方根
# 寻找x,满足x ^ 2 - k 在 (0, epsilon)范围内
def newton_raphson(k, epsilon):
guess = k
while abs(guess * guess - k) >= epsilon:
guess = guess - (((guess * guess) - k) / (guess * 2))
return guess
print(newton_raphson(2, 0.000000001))
二、二分查找法（Binary Search）
1.算法原理
如果x是大于1的数，则根号x一定位于0到x之间，此时我们用（暴力的）二分查找法求根号x的近似值，判定迭代结束的条件为abs(ans ^ 2 - x) < epsilon.
如果x是小于1大于0的数，则根号x位于0到1之间，此时我们在（0，1）区间内用二分查找法求解根号x的近似值，迭代结束的条件同上。
2.Python实现注意由于没有事先判定x的范围，所以查找上限变成了max(1.0, x). 下限为0.
# 使用二分查找求近似平方根
def bi_search_root(x, epsilon):
low = 0.0
high = max(1.0, x)
ans = (high + low) / 2.0
while abs(ans ** 2 - x) >= epsilon:
if ans ** 2 < x:
low = ans
else:
high = ans
ans = (high + low) / 2.0
return ans
print(bi_search_root(2, 0.000000001))
三、两种算法的效率比较
从时间复杂度上来看，牛顿法优于二分查找法。
我们可以对之前的代码进行简单的修改，以直观地看出这一区别：
将牛顿-拉弗森法的代码修改为：
# 利用牛顿-拉弗森法寻找平方根
# 寻找x,满足x ^ 2 - k 在 (0, epsilon)内
def newton_raphson(k, epsilon):
guess = k / 2.0
times = 0
while abs(guess * guess - k) >= epsilon:
guess = guess - (((guess * guess) - k) / (guess * 2))
times += 1
return guess, times
print(newton_raphson(2, 0.000000001))
times变量用于记录迭代求解的总次数。这里和以下的二分查找法的epsilon参数均设置为0.000000001.
将二分查找法的代码修改为：
# 使用二分查找求近似平方根
def bi_search_root(x, epsilon):
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low) / 2.0
while abs(ans ** 2 - x) >= epsilon:
numGuesses += 1
if ans ** 2 < x:
low = ans
else:
high = ans
ans = (high + low) / 2.0
return ans, numGuesses
print(bi_search_root(2, 0.000000001))
numGuesses变量用于记录迭代求解的总次数。
运行结果：牛顿法只用了四次迭代就得到了满意的近似值，而二分查找法则需要29次才能得到类似的结果。
(1.4142135623746899, 4) (1.4142135623842478, 29)总结
本文介绍了两种自定义求解根号的方法（Python实现），分别是牛顿-拉弗森法和二分查找法。牛顿-拉弗森法的时间复杂度比简单二分查找要低。
