分治法多项式乘法中子问题结果相加时间复杂度为Θ(n)的原因咨询

你产生误解的核心原因是把子问题的输出当成了单个数值，而实际上每个子问题返回的是完整的多项式系数序列，序列长度和输入规模n线性相关。

我们可以结合标准分治多项式乘法的逻辑推导：
假设我们要计算两个次数上限为n-1的多项式A(x)、B(x)的乘积，首先会将两个多项式拆分为高低半部分：

• A(x) = A0(x) + A1(x) * x^(n/2)，其中A0(x)是低n/2次项组成的多项式，A1(x)是高n/2次项组成的多项式
• B(x) = B0(x) + B1(x) * x^(n/2)，拆分规则同上

展开后的乘积公式为：
A(x)*B(x) = A0B0 + (A0B1 + A1B0) * x^(n/2) + A1B1 * x^n
这里的A0B0、A0B1、A1B0、A1B1就是4个子问题的输出，每个输出都是一个次数上限约为n的多项式，对应系数数组长度为O(n)。

合并阶段需要完成两类操作：

1. 移位：A0B1、A1B0的计算结果需要整体左移n/2位（对应系数数组前补n/2个0），A1B1的计算结果需要整体左移n位（对应系数数组前补n个0）
2. 逐位相加：把三个移位后的多项式的对应位置系数相加，得到最终乘积的系数数组

整个合并过程总共有约2n个系数位需要处理，每个系数位仅需要常数次加法操作，因此总的时间复杂度为Θ(n)，不可能是常数时间。

内容的提问来源于stack exchange，提问作者aex7214