Java中Horner算法用BigInteger时时间复杂度变为O(n²)的原因

我在实现计算多项式某点值的Horner算法，测试评估时间复杂度时发现：使用Integer类型时复杂度是O(n)，但换成BigInteger后，复杂度立刻变成近似O(n²)，这是为什么？

Integer类型实现代码 #

static int hornerAlgorithmInt(int poly[], int n, int x) {
    // Initialize result
    int result = poly[0];

    // Evaluate value of polynomial using Horner's method
    for (int i = 1; i < n; i++)
        result = result * x + poly[i];

    return result;
}

static int getResultInteger(int deg, int x) {
    int result;
    Random rd = new Random(); // creating Random object
    int[] arr = new int[deg];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = rd.nextInt(Integer.MAX_VALUE);// storing random integers in an array
    }
    long start = System.nanoTime();
    result = hornerAlgorithmInt(arr, deg, 3);
    long finish = System.nanoTime();
    System.out.println((finish - start) / 1000);
    return result;
}

BigInteger类型实现代码 #

static BigInteger hornerAlgorithmBig(BigInteger[] poly, int deg, BigInteger x) {
    BigInteger result = poly[0];
    for (int i = 0; i < deg; i++) {
        result = result.multiply(x).add(poly[i]);
    }
    return result;
}

static BigInteger getResultBig(String s, BigInteger x) {
    BigInteger[] polyCoefficient = arrayCreator(s);
    int deg = polyCoefficient.length;
    long start = System.currentTimeMillis();
    BigInteger result = hornerAlgorithmBig(polyCoefficient, deg, x);
    long finish = System.currentTimeMillis();
    System.out.println((finish - start));
    return result;
}

原因解析 #

核心差异在于基本类型与BigInteger的操作时间复杂度不同：

• Integer是Java的固定大小基本类型（32位），它的乘法、加法操作都是常数时间O(1)——不管数值是多少，CPU执行这些操作的时间固定。所以Horner算法的n次循环总复杂度是O(n)。
• BigInteger是任意精度的数值类型，它的内部用数组存储数字的每一位（或每一组位）。每次调用multiply()或add()时，操作时间和当前BigInteger的位数成正比：数值越大，位数越多，操作耗时越长。

在你的Horner算法中，每一步计算出的result都会不断增大（比如乘以x=3再加上系数），随着循环次数增加，result的位数是线性增长的。n次循环下来，总的操作次数近似为1+2+...+n = n(n+1)/2，也就是**O(n²)**的时间复杂度。

另外注意你的BigInteger版Horner算法有个小问题：循环从i=0开始，会多执行一次multiply(x).add(poly[0])，这会让结果出错，但不影响复杂度的结论。

内容的提问来源于stack exchange，提问作者Summa