java - 分析多项式和指数函数的运行时间

Question

所以我一直在尝试实现两个功能:

1. 在 O(d) 时间内执行整数多项式计算的方法，其中 d 是多项式的次数。

2. 计算幂。我需要它在 0(log b) 时间内执行

这是我到目前为止所想到的:

public static int polynomialEvaluation(int[] coefficients, int x){
    int n = coefficients.length -1;
    int y = coefficients[n];

    for (int i = n-1; i >= 0; i--){
        y = coefficients[i] + (x*y);

    }

    return y;
}


public static int exponentiation(int a, int b) {

    int res = 1;
    while (b > 0) {
        res = res * a;
        b--;
    }
    return res;
}

}

这两个中的任何一个满足时间复杂度要求吗？我想我有指数函数，但不确定第一个函数的成本。

编辑:我重写了指数函数，试图避免迭代循环，如下所示。我认为现在它的计算效率可能会更高

public static int exponentiation(int a, int b) {

    if ( b == 0) return 1;
    int res = exponentiation(a, b/2);
    if (a % 2 == 0)
        return res * res;
    else 
        return (a * res * res);
}

Answer 1

基本代数运算(例如加法和乘法)、数组查找和赋值都被认为需要常数时间。由于您的代码仅包含循环中的这些操作，因此复杂度是循环的迭代次数(加上外部操作的常量，但在 O 表示法中消失)。每个循环执行多少次迭代？

这有望告诉您多项式计算具有所需的复杂性，而指数计算则没有。更好算法的提示:如果您已经计算了 b²，那么使用该答案来计算 b⁴ 的最快方法是什么>？如果你得到了这个结果，你如何计算b⁸？如果您已经计算过，例如b²、b⁴、b⁸ 、b¹⁶、b³² 和b⁶⁴ 以这种方式(当然，您仍然拥有原始的 b¹)，您如何使用这些结果来计算例如b⁹³？