若对多项式的非零项采用链式存储法，如果两个多项式的非零项分别为n1个和n2个，最高项指数分别为m1和m2，则实现两个多项式相加的时间复杂度是多少

当使用链式存储法（即非零项链式）表示多项式时，实现两个多项式相加的时间复杂度主要取决于非零项的数量，因为每个非零项都需要进行一次加法操作[^1]。所以，无论最高项指数多大，只要非零项总数不变，时间复杂度就是O(n1 + n2)，其中n1和n2分别是两个多项式的非零项个数。

编程题示例（假设我们有两个已链式存储的多项式P1和P2）：

# 假设P1和P2的节点结构如下：
class PolynomialNode:
    def __init__(self, coefficient, exponent):
        self.coefficient = coefficient
        self.exponent = exponent
        self.next = None

# 相加操作
def add_poly(p1_root, p2_root):
    current1 = p1_root
    current2 = p2_root
    result_head = None
    carry = 0

    while current1 is not None or current2 is not None:
        if current1 is not None:
            temp_coeff = current1.coefficient
            current1 = current1.next
        else:
            temp_coeff = 0

        if current2 is not None:
            temp_coeff += current2.coefficient
            current2 = current2.next
        else:
            temp_coeff += carry

        carry = 0
        if temp_coeff > 0:
            new_node = PolynomialNode(temp_coeff % 10, temp_coeff // 10)
            if result_head is None:
                result_head = new_node
            else:
                last_node.next = new_node
            last_node = new_node
            if carry > 0:
                carry = 1  # 携带到下一位

    if carry > 0:
        new_node = PolynomialNode(carry, 0)
        if result_head is None:
            result_head = new_node
        else:
            last_node.next = new_node

    return result_head

# 使用上述函数添加两个多项式
p1_root = ...  # P1的根节点
p2_root = ...  # P2的根节点
result_head = add_poly(p1_root, p2_root)