数组每次扩容1个时插入n个新元素的时间复杂度求解及验证

现有一个大小为n的数组用于存储数据，当数组溢出时，会创建一个新数组，将旧数组所有元素复制到新数组中，且新数组仅比旧数组大1个位置。当前数组已占用√n个位置，请问插入n个新元素的时间复杂度是多少？

我的分析过程：

• 数组初始已占用√n个元素，剩余可用位置为n - √n。先插入n - √n个元素后数组已满，还剩√n个元素需要插入，因此需要重复√n次“创建新数组（每次扩容1个位置）”的操作。

时间复杂度拆解：

1. 向原数组插入n - √n个元素的时间复杂度为O(n)；
2. 将大小为n的数组复制到大小为n+1的新数组，时间复杂度为O(n)；
3. 插入额外元素的时间复杂度为O(1)。

其中步骤2和3需要执行√n次，总时间复杂度计算为：O(n) + √n*O(n) + √n*O(1) = Θ(n√n)。请问这个结论是否正确？

你的结论是正确的，我们可以再细化验证这一结果：

• 前n - √n次插入：每个插入都是直接操作数组空闲位置，时间复杂度为O(1)，总时间为O(n)，这部分无问题。
• 剩余√n次插入的复制操作：第一次复制时数组大小为n，第二次为n+1，直到最后一次为n + √n -1。复制操作的总时间是求和式：n + (n+1) + (n+2) + ... + (n + √n -1)。
  这个求和可以拆分为两部分：√n * n加上0+1+2+...+(√n-1)。后半部分的求和结果为(√n-1)*√n/2，属于O(n)量级（因为(√n)^2 = n），因此复制操作的总时间为Θ(n√n) + O(n) = Θ(n√n)。
• 加上这√n次插入本身的O(√n)时间，整体时间复杂度由最高阶的Θ(n√n)主导，最终时间复杂度确实是Θ(n√n)。

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