为什么在有空位的固定数组中随机插入元素的时间复杂度为O(n)？

首先先明确操作的前提：我们讨论的是带空余预留空间的连续存储固定长度数组，插入位置是完全随机的，所有可插入位置的出现概率相等。

整个插入操作可以拆成3个步骤：

• 生成要插入的随机位置下标r，这一步操作耗时固定，属于O(1)复杂度
• 挪位操作：数组是连续存储的，要把新元素放到r的位置，必须把原本在r到当前数组最后一个有效元素之间的所有元素，统一往后挪1位，空出r的位置
• 写入新元素到r位置，更新数组的有效长度，这一步也是固定耗时的O(1)操作

整个操作的耗时大头完全来自挪位的步骤，我们可以简单计算平均需要移动的元素数量：
假设当前数组已经存入了k个有效元素，那么可插入的位置总共有k+1个（从下标0到下标k）：

插在最后一个位置（下标k）时，不需要移动任何元素，移动次数为0
插在倒数第二个位置（下标k-1）时，需要移动1个元素
插在第一个位置（下标0）时，需要移动k个元素

所有情况的移动次数总和是 0+1+2+...+k = k*(k+1)/2，除以总共有k+1种插入位置，平均移动次数就是 k/2。
时间复杂度计算中会忽略常数系数，当数组接近存满的时候k≈n，所以平均移动次数就是n/2，对应时间复杂度就是O(n)。

额外补充：很多人会和数组末尾插入的O(1)复杂度搞混，只有固定插入到数组最后一位、不需要挪动任何元素的时候才是O(1)，随机插入需要覆盖所有位置的概率，因此必须考虑移动元素的开销。

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