时间的简单的Java code的复杂性 [英] Time complexity of the simple java code

问题描述

如何确定时间这一code的复杂性？我想这modPow方法是最贵。

 导入java.math.BigInteger的;
公共类FermatOne
{
    公共静态无效的主要（字串[] args）
    {
         的BigInteger一个=新的BigInteger（2）;
         BigInteger的K =新的BigInteger（15）;
         BigInteger的C =新的BigInteger（1）;
         INT B = 332192810;
         BigInteger的N =新的BigInteger（2）;
         BigInteger的权力;
         功率= a.pow（B）;
         BigInteger的指数;
         指数= k.multiply（功率）;
         BigInteger的MOD;
         MOD = exponent.add（C）;
         BigInteger的结果= n.modPow（指数，MOD）;
         的System.out.println（结果是==＆GT;+结果）;
     }
}
 

解决方案

那么这个特殊的code确定性运行在 O（1）。

然而，在更一般的任意变量，乘（）将在 O（n日志n）的运行其中， N 是位的数量。

POW（）方法将在运行为O（log B）对小 A 和 B 。这是由幂的平方实现。为更大的值，比特数变大（线性地）等的乘法需要更多的时间。我把它留给你找出确切的分析。

我不是100％，约约 modPow细节（），但我怀疑它运行类似于 POW（）除非额外 MOD 在求幂的每一步的平方。因此，它仍然是 O（日志B）乘法的好处是位的数量由界log M的其中， M 是mod。

How to determine time complexity of this code ? I guess that modPow method is the most "expensive ".

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);    
     }    
}

解决方案

Well this particular code deterministically runs in O(1).

However, in more general terms for arbitrary variables, multiply() will run in O(nlog n) where n is the number of bits.

pow() method will run in O(log b) for small a and b. This is achieved by exponentiation by squaring. For larger values, the number of bits gets large (linearly) and so the multiplication takes more time. I'll leave it up to you to figure out the exact analysis.

I'm not 100% about the details about modPow(), but I suspect it runs similarly to pow() except with the extra mod at each step in the exponentiation by squaring. So it'll still be O(log b) multiplications with the added benefit that the number of bits is bounded by log m where m is the mod.

这篇关于时间的简单的Java code的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！