为什么k*k <= n优于k <= Math.sqrt(n)

Question

我在研究寻找原始数的算法，看到下面的陈述，我不明白为什么。

while (k*k <= n) 

比

while (k <= Math.sqrt(n))

是因为函数调用吗？调用函数使用更多的资源。

更新:正如@Codor所说的，我想我需要提到的是，k在循环中被更改，而n没有被更改。

因此，如果我以前存储Math.sqrt(n)并每次使用它，它会比每次k*k的倍数更有效吗？

Answer 1

显然，对Math.sqrt的调用使用浮点数学，这可能比乘法中使用的整数运算代价更高。另一方面，Math.sqrt只需要对循环进行一次评估，而对k*k的评估则需要几次评估。

Answer 2

让我们看看迭代的时间复杂性：

• i=2 ..i*iO(sqrt(n))
• i=2 ..平方特(N) O(sqrt(n)*log(n))
• i=2 ..O(sqrt(n)) + O(log(n)) (牛顿法)
• i=2 ..sqrt ( Math.sqrt) O(sqrt(n))

但是，正如您编辑的，预先计算的平方根比每次必须在循环中执行的乘法更有效。