Math.sqrt Java的时间复杂度
Math.sqrt Java的时间复杂度
提问于 2015-03-03 00:57:33
在Java中实现math.sqrt的时间复杂度是多少？Java在某种技术中实现了时间复杂度，我正在尝试确定其时间复杂度。
回答 2
Stack Overflow用户
发布于 2015-03-03 01:06:25
在大多数情况下，Java尝试使用"smart-power“算法，其时间复杂度为O(log )。Smart power Algorithm
而且，在不同的情况下，您可能会得到不同的复杂性；Why is multiplied many times faster than taking the square root?
Stack Overflow用户
发布于 2015-03-03 01:06:32
它看起来像是通过委托给sqrt方法StrictMath实现的，这是一个本机方法。
因此，答案似乎是特定于实现的。
严格地说，它是O(1)。在理论上(但显然不是实践)，我们可以迭代所有的doubles并找到最大时间。
此外，Math.sqrt(n)的时间复杂度并不直接依赖于n，而是取决于表示n所需的空间量，对于doubles来说，n应该是常数。(N)的时间复杂度不直接依赖于n，而是取决于表示n所需的空间量。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28815339
复制相关文章
相似问题
腾讯云开发者
