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但找不到它。这篇 SO 帖子适用于 C# 并说它的 O(1)，而这篇 Java 帖子说它的 O(1) 但可能会迭代所有双打。

我试图了解这种方法的最坏时间复杂度。所有其他操作都是 O(1) 所以这是唯一的因素。将不胜感激任何反馈！

Answer 1

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

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

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