5

我们有一个测试练习，您需要找出给定的 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)，所以这是唯一的因素。任何反馈将不胜感激！

4

3 回答 3

5

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

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

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

于 2016-02-20T14:27:43.767 回答
1

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

于 2016-02-20T14:03:01.743 回答
0

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

于 2016-02-20T13:55:51.917 回答