algorithm - 这种检查数字 k 是否可以表示为 n^p 的方法的时间复杂度是多少

Question

以下方法的时间复杂度？我将其计算为 log(n)*log(n)= 日志(n)

public int isPower(int A) {
    if (A == 1) 
        return 1;

    for (int i = (int)Math.sqrt(A); i > 1; i--){
        int p = A;

        while (p % i == 0) {
            p = p / i;
        }

        if (p == 1) 
            return 1;
    }

    return 0;
}

Answer 1

最坏情况复杂度:
for(..)运行 sqrt(A)次

然后while(..)取决于 A=p_1^e1*p_2^e_2*..*p_n^e_n 的质因数分解，所以是 Max(e_1,e_2,..,e_n)最坏的情况，或大致 Max(log_p_1(A),log_p_2(A),..)
最多 while(..)将执行 log(A)次大致。

所以总粗略的最坏情况复杂度 = sqrt(A)*log(A)省略恒定因素

最坏情况的复杂性发生在数字 A它们是不同整数的乘积，即 A = n_1^e_1*n_2^e_2*..
平均案例复杂度:

给定的数字比不同整数的乘积多于简单的单个整数幂的数字，在给定范围内，然后随机选择一个数字，更有可能是不同整数的乘积，即 A = n_1^e_1*n_2^e_2.. .因此，平均情况复杂度与最坏情况复杂度大致相同，即 sqrt(A)*log(A)
最佳情况复杂度:

最佳情况复杂度发生在数字 A 时确实是单个整数/素数的幂，即 A = n^e .那么这种情况下的算法花费的时间更少。我把它作为计算最佳情况复杂度的练习。

附注。理解这一点的另一种方法是理解检查一个数是否是素数/整数的幂，实际上必须将这个数分解为素数分解(这是在这个算法中完成的)，这实际上是相同的复杂性(参见例如 complexity of factoring by trial division )。

所以应该有 mathjax 支持，因为 cs.stackexchange 有 :p !