有序数组插入m个中间元素的操作数计算与均摊时间复杂度咨询

一、m次插入的总操作数计算 #

因为数组是顺序存储结构，插入到中间位置时，需要把插入点之后的所有元素向后移动一位来腾出空间。具体的操作数可以通过累加每次插入的移动次数得到：

• 初始数组长度为n，第一次插入需移动 $\lceil \frac{n}{2} \rceil$ 个元素（不管n是奇数还是偶数，中间位置后的后半段元素都要后移）
• 插入后数组长度变为n+1，第二次插入需移动 $\lceil \frac{n+1}{2} \rceil$ 个元素
• 以此类推，第m次插入前数组长度为n+m-1，需移动 $\lceil \frac{n+m-1}{2} \rceil$ 个元素

将这m次移动次数累加，可以用数学公式简化计算：
总操作数 = $\lfloor \frac{(n+m)^2}{4} \rfloor - \lfloor \frac{n^2}{4} \rfloor$

如果用近似值表示（n和m较大时误差可忽略），总操作数约为 $\frac{nm}{2} + \frac{m^2}{4}$。

举个验证例子：

• 初始n=4，插入m=2次：总操作数为 $\lfloor \frac{6^2}{4} \rfloor - \lfloor \frac{4^2}{4} \rfloor = 9 - 4 = 5$，对应第一次移动2个元素、第二次移动3个元素，总和与计算结果一致。

二、均摊时间复杂度 #

均摊时间复杂度是总操作数除以插入次数m，代入近似值后，单次插入的均摊操作数约为 $\frac{n}{2} + \frac{m}{4}$，因此均摊时间复杂度为 O(n + m)。

分两种典型场景看：

• 当插入次数m远小于初始数组长度n时，均摊时间复杂度近似为O(n)，此时每次插入的开销主要由初始数组的长度决定
• 当插入次数m远大于初始数组长度n时，均摊时间复杂度近似为O(m)，此时数组长度随插入不断增长，每次移动的元素数也随之线性增加

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