java - 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 的复杂性，但找不到。 This SO post适用于 C# 并表示其 O(1) 和 this Java post说它的 O(1) 但可能会遍历所有 double 。

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

Answer 1

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

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

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