java - 简单java代码的时间复杂度

Question

如何确定这段代码的时间复杂度？我猜 modPow 方法是最“昂贵”的。

import java.math.BigInteger;    
public class FermatOne    
{    
    public static void main(String[] args)    
    {    
         BigInteger a = new BigInteger ("2");    
         BigInteger k = new BigInteger ("15");    
         BigInteger c = new BigInteger ("1");    
         int b = 332192810;    
         BigInteger n = new BigInteger ("2");    
         BigInteger power;    
         power = a.pow(b);    
         BigInteger exponent;    
         exponent = k.multiply(power);    
         BigInteger mod;    
         mod = exponent.add(c);    
         BigInteger result = n.modPow(exponent,mod);    
         System.out.println("Result is  ==> " + result);    
     }    
}

Answer 1

这个特定的代码确定性地在 O(1) 中运行。

但是，对于任意变量，multiply() 将在 O(nlog n) 中运行，其中 n 是数字位。

pow() 方法将在 O(log b) 中运行，用于小的 a 和 b。这是通过 exponentiation by squaring 实现的.对于较大的值，位数会变大(线性)，因此乘法需要更多时间。我会把它留给你来找出确切的分析。

我不是 100% 了解 modPow() 的细节，但我怀疑它的运行方式与 pow() 类似，除了额外的 mod 在平方求幂的每一步。所以它仍然是 O(log b) 乘法，还有一个好处是位数受 log m 限制，其中 m 是模组。