> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/computer-science/shu-ju-jie-gou-he-suan-fa/shu-zu-he-dong-tai-shu-zu.md).

# 数组和动态数组

## 动态数组

动态数组并不是真正意义上的动态的内存，而是一块连续的内存，当添加新的元素时，容量已经等于当前的大小的时候(存不下了)，执行下面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](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-1654fe5fd2deeed992d90880996a7c556d761859%2F32cbe4d2be1e2d1105cc59bd00b148fc.svg?alt=media)

当q != 1时：

![img](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-4c62fcfd9fc002d0e2782096e0e0961a153aa55b%2Fde92cc5e4793ae038e4297e83971154a.svg?alt=media)

或

![img](https://2351062869-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F7b2CdwBN9liniVJpfEAc%2Fuploads%2Fgit-blob-cfa9ab57b2c0fc1a5cac9b9e2e427869e448bfa8%2F842fdf9264ec2466cebdc60ba3daf499.svg?alt=media)

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