time-complexity - 如何正式计算朴素多项式评估在某一点的运行时间

Question

我直观地理解为什么朴素多项式评估在一点的时间复杂度是 ϴ(n^2)。但是，我不确定如何正式计算运行时间以显示它。

提前致谢！

标签： time-complexitypolynomials

Answer 1

不完全是ϴ(n^2)，而是ϴ(mn)， wherem和n是每个多项式中的项数。

需要简单的m * n乘法，等于a_i * b_j在两个多项式之间配对系数的方法的数量。

还有一些需要考虑的补充；但是，由于任何特定的一对系数a_i, b_j只属于 的一次幂，因此在最终多项式中x，它只会与一个系数相加一次。因此，最多只能有O(mn)添加。

因此，朴素乘法的整体时间复杂度为ϴ(mn)。