java - 检查一个数字是否是两个数字的幂的函数的时间复杂度

Question

我编写了一个解决方案来检查数字(N)是否可以表示为

其中 A > 0 且 P > 1。我认为这个解决方案的复杂度是 O( )

但我不确定日志的基础，也没有数学解释，我只是了解循环的工作原理，这帮助我得出了结论。

public int isPower(int A) {
    for (int i = 2; i <= Math.sqrt(A); i++) {
        for (int j = 2; j <= (Math.log(A) / Math.log(i)); j++) {
            if ((int)Math.pow(i, j) == A)
                return 1;
        }
    }
    return (A == 1) ? 1: 0;
}

我正在准备面试，任何解决方案将不胜感激，并将帮助我更好地准备。另外，如果您认为这个问题可以比我的算法更快地完成，请告诉我。

Answer 1

感谢 Ashwin 纠正解决方案。

您不需要再次完全迭代第二个循环，并且只需执行一次值检查。示例代码如下所示。

public int isPower(int a) {
        if (a == 1) {
            return 1;
        }
        for (long i = 2; i * i <= a; i++) {
            final double value = Math.log(a) / Math.log(i);
            if (value - (int) value < 0.00000001) {
                return 1;
            }
        }
        return 0;
    }

该解的复杂度为 O(sqrt(n))。我认为这是最有效的解决方案。