Как формально рассчитать время выполнения наивной полиномиальной оценки в точке

Question

Я интуитивно понимаю, почему временная сложность наивного полиномиального вычисления в точке равна ϴ (n ^ 2).Однако я не уверен, как формально рассчитать время выполнения, чтобы показать его.

Заранее спасибо!

Answer 1

Не совсем ϴ(n^2), но ϴ(mn), где m и n - количество членов в каждом полиноме.

Требуется тривиальное m * n умножение, равное количеству способов сопряжения коэффициентов a_i * b_j между двумя полиномами.

Есть также дополнения, которые следует рассмотреть;однако, поскольку любая определенная пара коэффициентов a_i, b_j принадлежит только одна степень x, она будет добавлена ​​ только один раз к коэффициенту в конечном полиноме.Следовательно, может быть только до O(mn) сложений.

Поэтому общая временная сложность наивного умножения составляет ϴ(mn).