矩阵乘法计算量估算：用栈模拟括号表达式与机考实战解析

1. 这道题想考的根本不是数学是括号与栈群里聊华为机考的时候矩阵乘法计算量估算这道题总会被翻出来。理由很直接它出现的频率不低分值也算可观而且难度刚好卡在一个让人又爱又恨的位置——弄懂套路的人五分钟写完没见过的人能在表达式解析上耗一晚上。这道题表面上是在考矩阵乘法实际上是在考两件事第一你是否清楚矩阵乘法的计算量怎么算第二你能不能把一个带括号的表达式按顺序模拟成一个逐步归约的过程。第二件事说白了就是栈的应用。先说清楚题目到底长什么样。一般形式是这样3 50 10 10 20 20 5 (A(BC))第一行是矩阵个数 N后面 N 行每行给出一个矩阵的行数和列数最后一行是一个只包含大写字母和左右括号的表达式。表达式里的 A 代表第一个矩阵B 代表第二个C 代表第三个以此类推。括号指明了矩阵乘法的结合顺序题目要你按照这个顺序把整个表达式实际执行一遍矩阵乘法所消耗的标量乘法次数统计出来。规则里 (A(BC)) 表示先算 B×C再用 A 去乘结果。这道题的核心考点其实很集中矩阵维度信息的组织、括号表达式的解析、栈的入栈出栈时机以及对“左矩阵列等于右矩阵行”这个合法条件的判断。很多备考的人一开始容易陷入误区以为要用区间 DP 求最优加括号方式实际上完全不需要——表达式已经给你加好括号了你要做的只是模拟不是优化。所以这篇文章会从矩阵乘法计算量这个基本概念出发手把手把栈模拟的算法拆开给出完整可运行的代码再把机考里容易踩的边界问题逐个讲清楚。无论你是刚接触机考的应届生还是刷了一段时间但被这类表达式题卡住的老手这篇都值得你花半小时看完并照着跑一遍。2. 为什么矩阵乘法的计算量会随顺序浮动2.1 一条乘法公式推到底矩阵乘法的计算量不是看两个矩阵长什么样而是看它们的维度配合关系。假设矩阵 A 是 m×n矩阵 B 是 n×p那么 A×B 的结果矩阵是 m×p。结果矩阵里一共有 m×p 个元素每个元素要由 A 的这一行与 B 的这一列做 n 次乘加运算得到。所以总标量乘法次数就是m × n × p注意这里统计的是标量乘法次数也就是最内层循环执行乘法的次数。加法次数不在题目统计范围内机考也不关心。很多初学者把 n 和 p 的位置搞混导致公式写错实际上记住一句话就行左矩阵的行数 × 左矩阵的列数 × 右矩阵的列数。维度满足什么条件才能相乘左矩阵的列数必须等于右矩阵的行数。这个条件也是判断表达式是否合法的关键。如果 A 是 3×5B 是 5×7那可以乘结果是 3×7如果 A 是 3×5B 是 4×7那就直接报错乘不了。2.2 用 50×10、10×20、20×5 这三个矩阵感受差距光看公式还体会不到计算顺序的影响我们拿题目示例里的三个矩阵算一遍。三个矩阵分别是矩阵行列A5010B1020C205先算 (A(BC)) 这个顺序。第一步算 B×CB 是 10×20C 是 20×5乘法次数是 10×20×5 1000结果是 10×5 的矩阵。第二步算 A×BC 的结果A 是 50×10BC 结果是 10×5乘法次数是 50×10×5 2500结果是 50×5。总次数 1000 2500 3500。再试试 (AB)C 这个顺序。第一步 A×B50×10×20 10000结果是 50×20第二步结果矩阵乘 C50×20×5 5000总次数是 10000 5000 15000。同一个三个矩阵仅仅改变括号位置计算量从 3500 跳到了 15000差了四倍多。这就是为什么机考要给你指定的括号顺序——因为不同顺序导致的计算量可能天差地远。你必须严格按照表达式里的括号去计算不能自己调整顺序也不能想当然地认为“矩阵乘法满足结合律所以顺序无所谓”。数学上结果矩阵确实相同但计算量完全不同。3. 用栈把表达式变成计算过程3.1 算法怎么设计理解了计算量公式之后剩下的问题就是怎么把 (A(BC)) 这种字符串变成一步步的乘法操作。这里要抓住括号表达式的本质最内层的括号一定是最先被计算的。在 (A(BC)) 中最内层括号是 (BC)所以 B×C 先算算完得到一个新矩阵然后再与 A 继续算。这种“最早进入的括号最后算完”或者反过来“最内层先算”的结构天然符合栈的特性。算法的整体设计可以这样描述先把 N 个矩阵的维度存起来。按照题目的默认约定第一个矩阵是 A第二个是 B依此类推。准备一个空栈栈里放的是矩阵的维度信息每个元素是一个二元组 (行数, 列数)。从左到右遍历表达式字符串遇到左括号 (什么都不做跳过遇到大写字母把这个字母对应的矩阵维度压入栈遇到右括号 )说明一个括号内的乘法子表达式可以归约了。此时栈里应当已经有了两个矩阵或者更准确地说当前括号范围内的矩阵都已经在栈里弹出两个矩阵做一次乘法乘法次数累加到答案上再把结果矩阵的维度压回栈供外层继续使用。遍历结束后栈里应该只剩下一个矩阵表示整个表达式归约完成。这个流程和计算器解析四则运算的思路一模一样右括号是触发求值的信号遇到右括号就弹栈、计算、压回结果。只不过这里不需要处理运算符优先级因为括号已经替你定好了顺序。3.2 弹出顺序为何是坑栈模拟里最容易翻车的地方是弹出顺序。很多人第一次写直接写 right stack.pop()left stack.pop()结果发现两个矩阵搞反了。原因很简单栈是后进先出后压入的矩阵在栈顶。我们处理 (AB) 时先读 A 压栈再读 B 压栈栈顶是 B。遇到右括号时第一次弹出的是 B它是乘法中位于右边的矩阵第二次弹出的才是 A是左边的矩阵。所以正确写法是right stack.pop() left stack.pop()先弹出的是右操作数后弹出的是左操作数。如果写反了虽然维度的数值在有些情况下碰巧不影响公式结果但一旦遇到行列数不对称的矩阵对会直接算错。务必养成用 left、right 命名变量的习惯别用 a、b 这种模糊名字。3.3 复杂度为什么是最优的这个算法的时间复杂度是 O(L)L 是表达式字符串的长度。每个字符只会被遍历一次每个矩阵维度至少被压栈一次某些中间结果矩阵还会被压栈一次但所有操作的总次数和表达式长度是线性关系。空间复杂度是 O(N)因为栈里最多同时存在 N 个矩阵维度信息。在机考环境下N 通常在 100 以内表达式长度也不会特别夸张这种复杂度完全够用不需要再做任何优化。相比之下如果题目不给括号顺序让你自己找最佳结合方式那就是经典的矩阵链乘法需要用区间 DP复杂度 O(N^3)。但华为机考的这道题限定好了括号就是为了考察你能不能写一个 O(L) 的栈模拟不要自己加戏去写 DP。4. Python 实现直接把上面的思路跑起来4.1 完整代码我平时练习和机考都用 Python因为写起来快调试也方便。下面这段代码是我实际测试过可以直接通过的版本输入输出格式按照最常见的数字版本来处理。import sys def compute(n, dims, expr): # dims 是 [(r0, c0), (r1, c1), ...]按顺序对应 A, B, C... mp {chr(ord(A) i): dims[i] for i in range(n)} stack [] total 0 for ch in expr: if ch (: continue if ch.isalpha(): stack.append(mp[ch]) elif ch ): # 至少需要两个矩阵才能做乘法 if len(stack) 2: return None right stack.pop() left stack.pop() # 合法性检查左矩阵的列必须等于右矩阵的行 if left[1] ! right[0]: return None total left[0] * left[1] * right[1] stack.append((left[0], right[1])) # 其他字符按非法处理或直接忽略题目保证不会有 # 合法结束时栈里应该只剩一个最终结果矩阵 if len(stack) ! 1: return None return total def main(): data sys.stdin.read().strip().split() if not data: return idx 0 outputs [] while idx len(data): n int(data[idx]) idx 1 dims [] for _ in range(n): r int(data[idx]) c int(data[idx 1]) idx 2 dims.append((r, c)) expr data[idx] idx 1 res compute(n, dims, expr) outputs.append(str(res) if res is not None else error) sys.stdout.write(\n.join(outputs)) if __name__ __main__: main()4.2 关键代码行解读为什么用一个 mp 字典因为表达式里直接给的是字母我们要通过字母找到对应的维度。默认约定第 0 个矩阵是 A第 1 个是 B所以用 chr(ord(A)i) 生成名字。这样代码读起来干净也不会出现字母序号对应错误。遍历到右括号时的处理是核心。为什么 total 累加的是 left[0] * left[1] * right[1]对照公式左矩阵行、左矩阵列、右矩阵列正好是 m×n×p。这里 left[1] 和 right[0] 在合法条件下是相等的千万别在累加公式里误写成一个 left[1] 一个 right[0]结果虽然数值相等但语义不对容易把合法性判断搞混。把结果矩阵 (left[0], right[1]) 压回栈是为了继续参与外层乘法。比如 (A(BC)) 中BC 的结果是 10×5这个结果要作为右矩阵和 A 相乘所以必须放回栈里等待外层右括号触发下一次弹出。4.3 本地验证样例代码写完之后建议先用示例跑一遍。把输入保存为文本比如 input.txt3 50 10 10 20 20 5 (A(BC))然后在命令行执行python solution.py input.txt预期输出是 3500。再多测两个样例。第一个是 (AB)C输入3 50 10 10 20 20 5 ((AB)C)按前面手算的结果输出应该是 15000。第二个是非法情况比如2 10 20 10 20 (AB)A 是 10×20B 是 10×20左矩阵列 20 不等于右矩阵行 10程序应该输出 error。我用这些样例测过都能得到预期结果。5. 这些边界情况不处理机考照样白给5.1 输入输出格式的坑华为机考这道题在不同年份、不同批次的题库里出现过细微的输入差异。最常见的一种是每行只给两个数字按顺序对应 A、B、C另一种是每行给三个内容比如 A 50 10矩阵名显式写在前面。这两种我都在网上见过也都有人栽在上面。如果你不想在考场上临时改代码建议在解析输入时兼容两种格式。最简单的方法是读入后判断每行元素的个数如果一行有三个 token就取第一个作为矩阵名后两个作为行列数如果只有两个 token则按默认字母顺序分配名字。这样无论出题人用哪种格式你的代码都能直接 AC。上面给的代码只处理了纯数字格式但你已经能看懂逻辑花一分钟改成兼容版本并不难。5.2 非法输入的防御题目一般会保证括号是匹配的但矩阵维度之间的关系不一定合法。比如两个矩阵相乘时维度不匹配整个表达式就无法计算。这种时候题目通常要求输出 error。我建议在代码里做两层防御第一层弹出时检查栈中是否至少有两个矩阵。如果表达式异常的句子导致 len(stack) 2说明括号不匹配或者字符有问题直接返回 None。第二层判断 left[1] 是否等于 right[0]不等就返回 None。很多人在本地手写测试时只测合法用例想着题目会保证格式结果考场上遇到一个意外的不合法用例就把代码打回原形。防御逻辑别嫌多反正代码量很小。5.3 数据类型与溢出的选择矩阵维度虽然单个看起来不大但连乘累加之后可能非常惊人。假设维度最大到 1000连续三层乘积就是 10^9 量级如果表达式嵌套很深中间结果多次累加总量很容易超过 32 位整数的范围。C 选手必须用 long long 存答案最好连栈里的维度也用 long long。Python 用户没有这个烦恼因为整型不会溢出但面试或机考的评分系统不一定只看 Python所以这个点还是要知道。我见过有人 C 用了 int最后答案溢出导致死活 AC 不了检查半天才发现数据类型的问题。5.4 一个容易被忽视的事实表达式最后要剩一个矩阵遍历完表达式后栈里应该只有一个最终结果矩阵。有些人不做这个检查直接输出 total。如果输入里矩阵个数和表达式字母出现次数不一致或者括号整体结构有问题total 可能是错乱的栈里可能剩两个甚至更多矩阵。加上这个检查就能把一类隐蔽错误拦在外面。6. 同类题目的套路迁移与机考备考建议6.1 括号类题型的通用解法做多了会发现华为机考很多中档题都在考同一个底层能力解析表达式。基本计算器、字符串解码、括号生成本质上都是在用栈维护一个“遇到闭合符号就归约”的过程。掌握了矩阵乘法这道题你在机考中遇到别的括号类题目时至少能快速想到栈这个方向。我给大家一个记忆口诀遇到左括号不管或压左括号哨兵遇到右括号就弹栈、计算、压回结果。如果题目里还涉及优先级比如加号和乘号混合就在弹栈时根据运算符优先级判断是否提前计算。矩阵乘法这道题没优先级已经是最简单的版本。6.2 没有括号时怎么算矩阵链 DP如果把这个题改一下不给括号表达式让你自己选择最佳计算顺序问题就变成矩阵链乘法。经典解法是区间 DP用 dp[i][j] 表示从第 i 个矩阵乘到第 j 个矩阵的最小计算量状态转移时枚举最后一个乘法的切分点 kdp[i][j] min(dp[i][k] dp[k1][j] dims[i-1] * dims[k] * dims[j])这个不是今天这道题的范围但如果你把栈模拟题做透了再去学矩阵链 DP理解会快很多。机考如果考到矩阵相关往往是在这两个方向里挑一个有括号就是栈无括号就是 DP。6.3 备考节奏建议我自己准备机考的体会是这类题目不要只刷一遍。第一遍照着题解打出来第二遍合上书自己从头写第三遍试着改一改输入格式、加一加防御逻辑。三次下来栈的使用就长在肌肉记忆里了。单独刷题之外还要给自己定时模拟机考的输入输出方式。很多人在 IDE 里跑通了就以为没问题结果因为不熟悉 OJ 的输入读取方式浪费大量时间。这一段代码要练到闭着眼能写出来你的机考胜算就又多了一点。