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

Question

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

$N = A^{P}$

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

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

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))。我认为这是最有效的解决方案。

Answer 2

更好的解决方案是对数字进行素因数分解，然后查看素数的幂是否具有不等于 1 的 GCD。如果你不明白我写的东西，我可以用代码更好地解释它。

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

Time complexity of a function which check if a number is power of two numbers

java

complexity-theory

big-o

time-complexity