向量的空间管理，有静态和动态两种策略
静态空间管理策略
开辟内部数组_elem[]并使用一段地址连续的物理空间，_capacity表示总容量 ，_size表示当前的实际规模n，示意图如下：
若采用静态空间管理策略，容量_capacity固定，则有明显的不足…
上溢/overflow： _elem[]不足以存放所有元素，尽管此时系统往往仍有足够的空间
下溢/underflow： _elem[]中的元素寥寥无几，装填因子 λ = _size / _capacity « 50%
动态空间管理策略
在即将上溢时，适当扩大内部数组的容量
递增策略
当需要扩容时，为_capacity追加固定大小的空间，即
T* oldElem = _elem; _elem = new T[ _capacity += INCREMENT ];
考虑最坏情况，在初始容量为0的空向量中连续插入n = m*I个元素
那么，在第1，I+1，2I+1，3I+1…次插入元素时都需要扩容，表示为
倍增策略
当需要扩容时，增加_capacity 为原来的两倍，即
T* oldElem = _elem; _elem = new T[ _capacity <<= 1 ];
考虑最坏情况，在初始容量为1的空向量中连续插入n = 2^m个元素
那么，在第1，2，4，8…次插入元素时都需要扩容，表示为
两种策略的复杂度分析
考虑最坏的情况，两种策略的复杂度分别为
- 递增策略： 为算术级数，0+
I+2I+…=O(n ²) - 倍增策略： 为几何级数，1+2¹+2²+2³+…=O(2^m)=O(n)
| 递增策略 | 倍增策略 | |
|---|---|---|
| 累计时间 | O(n ²) | O(n) |
| 分摊时间 | O(n) | O(1) |
| 装填因子 λ | ≈100% | >50% |
可以看出，倍增策略在牺牲空间的基础上，换取时间上的巨大提升，可采取√
注意这里用到了分摊分析的概念，区别于平均/期望分析