如何正式计算某点的朴素多项式求值的 运行 时间
How to calculate formally the running time of the naive polynomial evaluation at a point
我凭直觉理解为什么朴素多项式求值在一个点的时间复杂度是ϴ(n^2)。但是，我不确定如何正式计算 运行 时间以显示它。
提前致谢！
不完全是 ϴ(n^2)，而是 ϴ(mn)，其中 m 和 n 是每个多项式中的项数。
需要微不足道的 m * n 乘法，等于在两个多项式之间对系数 a_i * b_j 进行配对的方法数。
还有一些补充需要考虑；但是，由于任意一对系数a_i, b_j只属于x的一个次方，所以它只会被添加一次 到最终多项式中的系数。因此最多只能添加 O(mn) 次。
因此，朴素乘法的总体时间复杂度为ϴ(mn)。
我凭直觉理解为什么朴素多项式求值在一个点的时间复杂度是ϴ(n^2)。但是，我不确定如何正式计算 运行 时间以显示它。
提前致谢！
不完全是 ϴ(n^2)，而是 ϴ(mn)，其中 m 和 n 是每个多项式中的项数。
需要微不足道的 m * n 乘法，等于在两个多项式之间对系数 a_i * b_j 进行配对的方法数。
还有一些补充需要考虑；但是，由于任意一对系数a_i, b_j只属于x的一个次方，所以它只会被添加一次 到最终多项式中的系数。因此最多只能添加 O(mn) 次。
因此，朴素乘法的总体时间复杂度为ϴ(mn)。