用C++编写算法，输入整数n(1<=n<=1000)，x(1<=x<=1000)和ai（i=0,1,2,3，…n）的值，设计时间复杂度小于O(n2)的算法，求一元多项式

在C++中，对于给定的一元多项式 \( P(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \)，如果你需要计算该多项式的值，可以使用线性时间复杂度（O(n)）的多项式求值算法。这个算法利用了数学上多项式乘法的性质，称为 Horner's 方法（霍纳法则）。

#include <iostream>

// 计算多项式P(x)的值，a[]存储系数，n是多项式的阶数
int evaluatePolynomial(int a[], int n, int x) {
    int result = a[0]; // 初始化结果为常数项
    for (int i = 1; i <= n; ++i) { // 从最高次项开始到一次项
        result = result * x + a[i]; // 按照霍纳法则更新结果
    }
    return result;
}

int main() {
    int n, x;
    std::cout << "请输入多项式的阶数n(1 <= n <= 1000): ";
    std::cin >> n;
    std::cout << "请输入变量x的值(1 <= x <= 1000): ";
    std::cin >> x;

    // 假设你已经有了一个长度为n+1的一维数组a存储了多项式的系数
    int* coefficients = new int[n + 1];
    // ... (在这里读取或者初始化系数)

    int polynomial_value = evaluatePolynomial(coefficients, n, x);
    std::cout << "多项式P(" << x << ") 的值为: " << polynomial_value << std::endl;

    delete[] coefficients; // 别忘了释放内存
    return 0;
}

在这个例子中，输入多项式的系数并传递给`evaluatePolynomial`函数，然后输出多项式在特定x值下的值。算法的时间复杂度保持在O(n)。