java 中 Math.sqrt 的最坏情况时间复杂度

Question

我们有一个测试练习，你需要找出给定的 N 个数字是否是另一个数字的平方，时间复杂度最小。

我写了：

public static boolean what2(int n) {
    double newN = (double)n;
    double x = Math.sqrt(newN);
    int y = (int)x;
    if (y * y == n)
        return false;
    else
        return true;
}

我在网上查看，特别是在 SO 上，试图找到 sqrt 的复杂性，但找不到。 is for C# and says its O(1), and this Java post 说它的 O(1) 但可能会遍历所有双打。

我正在尝试了解此方法的最差时间复杂度。所有其他操作都是 O(1)，所以这是唯一的因素。非常感谢任何反馈！

Answer 1

java 的 Math.sqrt 实际上将 sqrt 委托给 StrictMath.java 可以找到其实现之一的源代码 here，通过查看 sqrt 函数，它看起来像复杂度是常数时间。看看里面的 while(r != 0) 循环。

Answer 2

如果我理解正确，Java 指令可以通过即时编译转换为使用本机 fsqrt 指令（但我不知道这是否是实际上是这种情况），根据 this table，它使用有限数量的处理器周期，这意味着复杂度为 O(1).

Answer 3

使用浮点转换是可以的，因为 java 的 int 类型是 32 位，而 java 的 double 类型是 IEEE 64 位格式可以精确表示32位整数的所有值。

如果要为 long 实现函数，则需要更加小心，因为许多大的 long 值并不完全表示为 doubles，因此采取平方根并将其转换为整数类型可能不会产生实际平方根。

您实现中的所有操作都在常数时间内执行，因此您的解决方案的复杂度确实是 O(1)。

java 中 Math.sqrt 的最坏情况时间复杂度

Worst case time complexity of Math.sqrt in java

java

math

time-complexity

math.sqrt