JavaScript-无需Math.sqrt即可找到完美平方的平方根的改进算法

用户名

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

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

最重要的是,我需要知道如何改善这种性能。我真的不在乎它的功能有限

伊凡·格里申科(Ivan Gritsenko)

我可以建议这是一个小改进。首先从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 2是递增函数。

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))运行时间复杂度。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档