js实现Math.sqrt开平方根

发表于 | 分类于 |

前言

有一次刷脉脉,在匿名区看到一道题目,好像LeetCode上有:二分法用实现Math.sqrt函数开平方根。想当年1.414、1.732、2.236、2.449背的滚瓜烂熟,甚至手写过开方计算。

分析

看到二分法就不由得想到数组的二分查找,在我的这篇博客二分法查找有代码。
二分法实现开方也是一样的道理,拿到最小值和最大值,取中间值,判断中间值的平方是否等于目标值,等于则返回,否则继续折半查找一步一步逼近正确值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function sqrtBisection(n) {
    if (isNaN(n)) return NaN;
    if (n === 0 || n === 1) return n;
    var low = 0,
        high = n,
        pivot = (low + high) / 2,
        lastPivot = pivot;
    // do while 保证执行一次
    do {
        console.log(low, high, pivot, lastPivot)
        if (Math.pow(pivot, 2) > n) {
            high = pivot;
        } else if (Math.pow(pivot, 2) < n) {
            low = pivot;
        } else {
            return pivot;
        }
        lastPivot = pivot;
        pivot = (low + high) / 2;
    }
    // 2018-04-25 22:08 更新
    // 使用Number.EPSILON表示能够接受的最小误差范围
    while (Math.abs(pivot - lastPivot) >= Number.EPSILON)

    return pivot;
}

然后我又google了一下发现大部分的解决方案都是用的牛顿迭代, 即切线逼近。高中大学学的那点数学知识基本上忘光了,公式看的我眼花,我就不献丑了,反正最后可以得出的方程式是 x = (x + n / x) / 2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function sqrtNewton(n) {
    if (n < 0) return NaN;
    if (n === 0 || n === 1) return n
    var val = n,
        last;
    do {
        console.log(val, last)
        last = val;
        val = (val + n / val) / 2;
    }
    // 2018-04-25 22:08 更新
    // 使用Number.EPSILON表示能够接受的最小误差范围
    while (Math.abs(val - last) >= Number.EPSILON)
    return val
}

比较两种方法的时间复杂度
二分法的时间复杂度固然是O(logN),牛顿法的复杂度我就不太明了了。看看两个函数对2000开平方所耗时间吧。

1
2
3
4
5
6
7
8
9
10
11
console.time('二分法耗时')
sqrtBisection(2000)
console.timeEnd('二分法耗时')

result: 二分法耗时: 7.697998046875ms

console.time('牛顿法耗时')
sqrtNewton(2000)
console.timeEnd('牛顿法耗时')

result: 牛顿法耗时: 1.44580078125ms