J'essaie d'apprendre des algorithmes et de coder des trucs par zéro. J'ai écrit une fonction qui ne trouvera que les racines carrées des nombres carrés, mais j'ai besoin de savoir comment améliorer ses performances et éventuellement retourner les racines carrées des nombres non carrés
function squareroot(number) {
var number;
for (var i = number; i >= 1; i--) {
if (i * i === number) {
number = i;
break;
}
}
return number;
}
alert(squareroot(64))
Reviendra 8
Plus important encore, j'ai besoin de savoir comment améliorer ces performances. Je ne me soucie pas encore vraiment de ses fonctionnalités limitées
5 réponses
Voici une petite amélioration que je peux suggérer. Premièrement - commencez l'itération à partir de 0. Seconde - quittez la boucle lorsque le carré du candidat racine dépasse le 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
}
Cet algo fonctionnera en O (√nombre) en comparaison avec le O (n) initial qui est en effet une amélioration des performances que vous avez demandée.
Modifier # 1
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;
}
Cet algo présente une O (log (nombre)) complexité de la durée d'exécution.
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;
}
Cela retournera la racine carrée en trouvant à plusieurs reprises la moyenne.
var result1 = squareRoot(25) //5
var result2 = squareRoot(100) //10
var result3 = squareRoot(15) //3.872983346207417
JSFiddle: https://jsfiddle.net/L5bytmoz/12/
La recherche binaire fonctionnera mieux.
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;
}
Les choses que vous essayez de faire s'appellent des méthodes numériques. La méthode numérique la plus rudimentaire / facile pour la résolution d'équations (oui, vous résolvez une équation x ^ 2 = a ici) est une Méthode Newtons.
Il vous suffit d'itérer cette équation:
Dans votre cas f(x) = x^2 - a et donc f'(x) = 2x.
Cela vous permettra de trouver une racine carrée de n'importe quel nombre avec n'importe quelle précision. Il n'est pas difficile d'ajouter une étape qui rapproche la solution d'un entier et vérifie si sol^2 == a
Sépare la méthode de Newton de la fonction à approximer. Peut être utilisé pour trouver d'autres racines.
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))