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

Question

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

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

这 2 个是否满足时间复杂度要求？我想我有指数函数，但不确定第一个函数的成本。

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

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⁹³?