数组和动态数组

动态数组

动态数组并不是真正意义上的动态的内存，而是一块连续的内存，当添加新的元素时，容量已经等于当前的大小的时候(存不下了)，执行下面3步

1. 重新开辟一块大小为当前容量两倍的数组

2. 把原数据拷贝过去

3. 释放掉旧的数组

动态数组的相关概念：

1. 初始大小，创建时可容纳的默认元素个数

2. 加载因子，表示某个阀值，用0~1之间的小数来表示，当已有元素占比达到这个阀值后，底层将进行扩容操作

3. 扩容方式/扩容增量，即指定每次扩容后的大小的规则，比如在golang中slice的扩容规则为翻倍，而java的ArrayList的扩容增量为* 0.5 + 1

扩容代价的时间复杂度：

动态数组需要额外的扩容操作来支持动态的功能，这些额外的操作就是扩容代价。

假设有一个数组长度为1，他的扩容方式为二倍，这里向数组中插入N个数，他的扩容代价如下：

• 数组长度为1，无需扩容

• 数组长度为2，需要扩容1次，拷贝元素1个

• 数组长度为4，需要扩容2次，拷贝元素2个

• 数组长度为8，需要扩容3次，拷贝元素4个

• 数组长度为16，需要扩容4次，拷贝元素8个

• ....

• 数组长度为N，需要扩容 logN次， 拷贝元素 2^(logN - 1)个

注意：我们只需要证明总共拷贝的元素个数是O(n)级别的就好了(因为释放内存和申请内存都比较快

故添加N个数到数组中，他的扩容代价为：1 + 2 + 4 + 8 + ....+ 2^(logN - 1)，根据等比数列公式：

当q == 1时：

img

当q != 1时：

img

或

img

这里公比q=2，首项a1=1，尾项尾 2^(logN - 1)， 故Sn = 2 ^(logN -1) -1 ，也就是 (1/2)N-1，故时间复杂度为 O(N)。因为插入N个数字的额外时间复杂度为O(N)，故插入一次的时间复杂度均摊后为O(1)。