设为一个数组，用于存放大小为n的数据溢出我们创建一个新数组，将旧数组中的所有元素复制到我们只是把新数组再大1个
如果数组大小为n，且第一个位置被占用的次数为√n。
插入n个新元素的时间复杂度是多少?
因为在n大小的数组中已经有√n个元素了。还有(n-√n)个空位留给大小为n的数组。我们将(n-√n)个空位插入到数组中我们还剩下√n个元素要插入。数组已满。所以我们要创建一个新数组√n次，并增加一个额外的位置。
时间复杂度:
- insert (n -√n) elements into origin array = 0 (n)
- 将数组大小n复制到新的数组大小n+1。- - - - - - O (n) 插入额外的元素。- - - - - - O (1)
我们必须做步骤2和3√n次。
总:O (n) +√nO (n) +√nO(1) =Θ(√n * n)
我的答案正确吗?
是。
没有提到的一个方面是，步骤2中的𝑛+1在第一次执行时只会恰好是𝑛+1，但会是𝑛+2，𝑛+3，…，𝑛+√𝑛
但是，如果我们总是假设每次执行该步骤为0(𝑛+√𝑛)，从而为复杂性创建一个上限，那么结果是相同的(我在这里排除了第一阶段的0(𝑛)):
O(√𝑛(𝑛+√𝑛))= O(𝑛√𝑛+𝑛)= O(𝑛√𝑛)