降低求平方整数的时间复杂性

Question

以下函数用于搜索范围a和b之间的平方整数。但问题是它超过了时间限制。该范围可以是1<a<b<10^9.

function squares(a, b) {
let count = 0;
while(a<=b)
{
if(Number.isInteger(Math.sqrt(a)))
{
count++;
}
a++;
}
return count;
}

有人能帮我降低这件事的复杂性吗？。

Answer 1

您可以尝试"创建"；他们

一个想法是找到一个，然后生成下一个，作为(n+1)^2-n^2=2n+1。这将是非常有效的，但我们可以做得更好。

由于你只需要计算平方数，我们可以简单地计算a和b的平方根，并计算这些平方根之间的整数数量(只需从另一个中减去一个(。但是当a和b中的一个本身是正方形时要小心。

因此，我们可以写以下内容：

function squares(a, b) {
const sqrtA = Math.sqrt(a)
const floorA = Math.floor(sqrtA)
const sqrtB = Math.sqrt(b)
const ceilB = Math.floor(sqrtB)

let n = ceilB -  floorA

if (floorA == sqrtA) { // A is a square
n += 1
}

return n
}