C++算法:如何提高此代码的效率?[大O]

Question

我怎样才能重新编写下面的代码，以提高他的效率？

Fraction Polynomial::solve(const Fraction& x) const
{
Fraction rc;
auto it = poly_.begin();
while (it != poly_.end())
{
Term t = *it;
//find x^exp
Fraction curr(1, 1);
for (int i = 0; i < t.exponent_; i++)
{
curr = curr * x;
}
rc += t.coefficient_ * curr;
it++;
}
return rc;
}

此代码的当前 Big-O 表示法是什么？[我认为是O(N^2)]

Answer 1

我将引用数字食谱，第5章，因为它很有趣：

我们假设你知道的足够多，永远不会计算多项式 道路：

p=c[0]+c[1]*x + c[2]*x*x +c[3]*x*x*x + c[4]*x*x*x*x;

或者(甚至更糟！

p=c[0]+c[1]*x+c[2]*pow(x,2.0)+c[3]*pow(x,3.0)+c[4]*pow(x,4.0);

来 (计算机)革命，所有被判犯有此类罪行的人 行为将被立即执行，而他们的程序不会被执行！它 然而，是否写作是一个品味问题

p=c[0]+x*(c[1]+x*(c[2]+x*(c[3]+x*c[4])));

或

p=(((c[4]*x+c[3])*x+c[2])*x+c[1])*x+c[0];

。

至少这会从O(m*n)实现中删除m(其中m是指数，n多项式阶)。