JavaScript - 改进在没有 Math.sqrt 的情况下查找完美平方根的算法

Question

我正在尝试从头开始学习算法和编码。我写了一个函数，它只会找到平方数的平方根，但我需要知道如何提高它的性能并可能返回非平方数的平方根

function squareroot(number) {
    var number;
    for (var i = number; i >= 1; i--) {
        if (i * i === number) {
            number = i;
            break;
       }
   }
   return number;
}

 alert(squareroot(64))

将返回 8

最重要的是，我需要知道如何提高性能。我还不太关心它的有限功能

Answer 1

这是我可以建议的一个小改进。第一 - 从 0 开始迭代。第二 - 当候选根的平方超过 number 时退出循环。

function squareroot(number) {
    for (var i = 0; i * i <= number; i++) {
        if (i * i === number)
            return i;
   }
   return number; // don't know if you should have this line in case nothing found
}

与初始 O(n) 相比，此算法将在 O(√number) 时间内运行，这确实是您要求的性能改进。

编辑#1

更有效的解决方案是按照@Spektre 的建议对答案进行二分搜索。已知 x² 是递增函数。

function squareroot(number) {
    var lo = 0, hi = number;
    while(lo <= hi) {
         var mid = Math.floor((lo + hi) / 2);
         if(mid * mid > number) hi = mid - 1;
         else lo = mid + 1;
    }
    return hi;
}

此算法的运行时间复杂度为 O(log(number))。