JavaScript

Question

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

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

 alert(squareroot(64))

会return8

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

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

Answer 2

您尝试做的事情叫做 numerical methods. The most rudimentary/easy numerical method for equation solving (yes, you solve an equation x^2 = a here) is a Newtons method。

你所要做的就是迭代这个等式：

你的情况 f(x) = x^2 - a 因此 f'(x) = 2x.

这将使您能够以任意精度求出任意数字的平方根。不难添加一个将解近似为整数并验证是否 sol^2 == a

的步骤

Answer 3

将牛顿法与要近似的函数分开。可用于查找其他根。

function newton(f, fPrime, tolerance) {
  var x, first;

  return function iterate(n) {
    if (!first) { x = n; first = 1; }

    var fn = f(x);

    var deltaX = fn(n) / fPrime(n);
    if (deltaX > tolerance) {
      return iterate(n - deltaX)
    }

    first = 0;
    return n;
  }
}


function f(n) { 
  return  function(x) { 
    if(n < 0) throw n + ' is outside the domain of sqrt()';
    return x*x - n;
  };
}

function fPrime(x) {
  return 2*x;
}


var sqrt = newton(f, fPrime, .00000001)
console.log(sqrt(2))
console.log(sqrt(9))
console.log(sqrt(64))

Answer 4

二分查找效果最好。

let number = 29;
let res = 0;

console.log((square_root_binary(number)));
function square_root_binary(number){

    if (number == 0 || number == 1)  
       return number;

    let start = 0;
    let end = number;


    while(start <= end){

        let mid = ( start + end ) / 2;

        mid = Math.floor(mid);

        if(mid * mid == number){
            return mid;
        }

        if(mid * mid < number){
            start = mid + 1;
            res = mid;
        }
        else{
            end = mid - 1;
        }
    }

    return res;
}

Answer 5

function squareRoot(n){
    var avg=(a,b)=>(a+b)/2,c=5,b;
    for(let i=0;i<20;i++){
        b=n/c;
        c=avg(b,c);
    }
    return c;
}

这将 return 通过重复求平均值来求平方根。

var result1 = squareRoot(25) //5
var result2 = squareRoot(100) //10
var result3 = squareRoot(15) //3.872983346207417

JSFiddle：https://jsfiddle.net/L5bytmoz/12/

Answer 6

这里是牛顿迭代法的解 -

/**
 * @param {number} x
 * @return {number}
 */
// newstons method
var mySqrt = function(x) {
    if(x==0 || x == 1) return x;

    let ans, absX = Math.abs(x);
    let tolerance = 0.00001;
    while(true){
        ans = (x+absX/x)/2;
        if(Math.abs(x-ans) < tolerance) break;
        x = ans;
    }
    return ans;
};

Answer 7

我在 Github 上看到了这个解决方案，这是在不使用任何外部库的情况下计算数字平方根的更好、最简单的方法

function TakingPerfectSquare(Num) {
   for (var i = 0; i <= Num; i++) {
      var element = i;
      if ((element == element) && (element*element == Num)) {
         return true;
      }
   }
   return false;
}
console.log(TakingPerfectSquare(25));

Answer 8

如果您分析所有自然数及其平方，您可能会发现一个规律...

Numbers   Squares   Additives
   1         1          3
   2         4          5
   3         9          7
   4        16          9
   5        25         11
   6        36         13
   7        49         15

查看正方形列中的第一行（即 1）并将其与添加剂列中的第一行（即 3）相加。您将得到四个，它们位于方块列的第二行。

如果你不断重复这个，你会发现这适用于所有自然数的平方。现在，如果您查看添加剂列，下面的所有数字实际上都是奇数。

要找到一个完美平方的平方根，您应该继续用连续的奇数（从 1 开始）减去它，直到它为零。可以减去的次数就是那个数的平方根。

这是我在打字稿中的解决方案...

function findSquareRoot(number: number): number {
  for (let i = 1, count = 0; true; number -= i, i += 2, count++) {
    if (number <= 0) {
      return number === 0 ? count : -1; // -1 if number is not a perfect square
    }
  }
}

希望这有更好的时间复杂度:)

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

JavaScript - Improving algorithm for finding square roots of perfect squares without Math.sqrt

algorithm

square-root