数组与线性结构
动态数组
动态数组是一种会自己长大的数组。它内部藏着一个普通数组（底层存储），再加两个数字：容量（已分配多少个槽位）和大小（实际用了多少个）。只要还有空位，追加元素就是把它放进下一个空槽——O(1)。C++ 的 std::vector、Java 的 ArrayList、Python 的 list 都是这样工作的。
当底层数组装满时，动态数组会分配一个更大的（通常是容量翻倍），把已有元素全部拷过去，再释放旧的。这一次追加很贵，是 O(n)，但翻倍意味着它很少发生：两次昂贵扩容之间，是一长串廉价的追加。平摊下来，每次追加仍然是 O(1)。这种平均叫做摊还 O(1)，而翻倍策略正是它成立的原因。
于是你保留了数组的 O(1) 下标访问，又摆脱了定长的限制。剩下的取舍与普通数组相同：在中间插入或删除仍然是 O(n)（要挪动元素），而且容量可能大于实际大小，所以会预留一点内存。
#include <vector>
std::vector<int> v; // size 0, capacity 0
for (int i = 0; i < 5; ++i)
v.push_back(i); // amortized O(1) each
// capacity grows like 1 -> 2 -> 4 -> 8 (implementation-defined)
int x = v[3]; // O(1) indexed access
v.insert(v.begin() + 1, 99); // O(n): shifts later elements大多数 push_back 都很便宜；偶发的翻倍拷贝被分摊到它们之中。
按常数倍数增长（如翻倍）才能得到摊还 O(1) 的追加；若每次只 +1 地扩容，整体追加会退化成 O(n)。
又称
另见