为什么精确计算解决方案比二进制搜索解决方案慢

Question

所以我试着做这个leetcode问题：https://leetcode.com/problems/arranging-coins/

经过一些数学运算，我想出了这个解决方案：

var arrangeCoins = function(n) {
return parseInt((Math.sqrt(8*n+1)-1)/2);
};

这确实返回了正确的答案。然而，我注意到，当谈到执行速度时，它实际上是桶的底部。相比之下，使用二进制搜索来搜索1到n范围内的正确值的替代解决方案比我的快大约2到3倍。这样的东西：

var arrangeCoins = function(n) {

let left = 1;           
let right = n;          

while(left + 1 < right){
let mid = Math.floor(left + (right - left) / 2);
let sum = (mid + 1) * mid / 2  

if(sum === n){
return mid;
}else if(sum < n){
left = mid;
}else{
right = mid;
}
}

return (right + 1) * right / 2 === n? right : left;
}

与我的解决方案相比，这具有O(logn(的时间复杂性，这意味着它应该更慢，至少在理论上是这样。

为什么会出现这种情况？我可以做些什么来提高解决方案的执行速度？

Answer 1

这不是一个权威的答案，但：

1. sqrt相对较慢
2. 看起来你的parseInt是无用的并且浪费时间