n位加法与乘法运算的有效时间复杂度说法求证

你的表述大部分符合学界和工业界的通用结论，只有两处细节需要修正：

• 固定字长高性能处理器的单字运算场景
  课程里提到的复杂度是经典硬件实现的标准结论，整体准确：
  • 加减运算采用超前进位加法器（CLA）实现时，进位传递延迟为O(log n)，是当前所有高性能CPU单字加减的标配实现，没有问题。
  • 经典的阵列乘法器、移位迭代除法的单字运算延迟确实为O(n)，需要补充的是：近年高端CPU用华莱士压缩树优化单字乘法后，延迟已经可以做到O(log n)，但绝大多数计算机体系结构入门教材仍会以经典实现的O(n)作为教学结论，不属于表述错误。
• 无固定字长限制的任意精度大数运算场景
  这部分有两个细节偏差：
  1. 加减运算的理论最优复杂度不是O(n)：O(n)是串行逐位进位加法的复杂度，也是当前工程实现里的实际可达上界（受限于逐位读取操作数的内存IO固有成本），但并行计算模型下已经存在O(log n)时间的加法算法，线性时间并非理论最优值。
  2. 你提到的O(n log n log log n)复杂度对应的是Schönhage–Strassen大数乘法算法，不是Strassen——Strassen算法是用于矩阵乘法加速的，属于人名记忆偏差。另外这个复杂度是1971年提出的经典大数乘除上界，目前学界已经证明大数乘除的理论复杂度可以逼近O(n log n)的下界，只是新算法的常数项极高，暂时没有工程实用价值。除法可以通过牛顿迭代归约为乘法运算，因此和乘法同复杂度的表述是准确的。

整体而言，你记忆的复杂度量级完全可以支撑常规的算法分析、体系结构相关的工程判断，两处细节偏差不影响核心结论的使用。

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