为何整数乘法的时间复杂度为O(n²)？求实例解析

首先要明确：时间复杂度描述的是算法运行时间随输入规模增长的趋势，这里的输入规模是数字的位数n，不是具体某个数字的操作次数。你用99×99数出的3次是“组合操作”，但时间复杂度要拆解到最底层的单个数字运算。

拿两位整数（n=2）的乘法来拆解：
把99拆成9×10 + 9，两个99相乘的展开式是：

(9×10 + 9) × (9×10 + 9) = 9×9×10² + 9×9×10 + 9×9×10 + 9×9

这里的底层操作是单个数字的乘法和对应位的加法：

• 单个数字乘法的次数：第一个数的每一位都要和第二个数的每一位相乘，两位数字就是2×2=4次（也就是四个9×9）
• 加法操作：把这些乘积按位对齐后相加（比如81×100、81×10、81×10、81相加），这部分需要处理进位，操作次数也是和n²成正比的。

你之前把99×9算成一次操作，但实际上99×9本身是两位乘一位的运算，它内部包含了2次单个数字乘法（9×9和9×9），以及后续的加法进位操作——这些底层操作才是时间复杂度统计的对象。

推广到n位整数的情况：两个n位数字相乘，必然要完成n×n次单个数字的乘法，再加上O(n²)次加法来合并结果，所以整体时间复杂度是O(n²)。

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