第二章：向量本文为邓俊辉老师的《数据结构(C++版)》第三版学习笔记
全书代码示例下载：链接【点击跳转】
- 一、抽象类型数据结构
- 1.接口与实现
- 2.向量 ADT
- 3.vector 析构与构造
- 4.复制
- 5. 习题
- 二、可扩充向量
- 1。固定向量的缺点
- 2.动态空间管理
- 3.递增式扩容
- 4.加倍式扩容
- 5. 分摊复杂度 (分摊分析法)
- 三、无序向量
- 1. 实现
- 2.有序 逆序程度
- 3.唯一性
- 4.二分 O(logn) 减而治之
- ADT 抽象数据类型
array
待学完补充 vector实现
5. 习题 二、可扩充向量 1。固定向量的缺点 2.动态空间管理 3.递增式扩容开辟可以大一点的空间，避免在接下来足够长的时间内，不会因为有必要扩容，而打断接下来计算过程。
- 按固定增量进行扩容 时间复杂度 O(
n
2
n^2
n2) 空间复杂度 O(n)
- 按俩倍 进行扩容 时间复杂度 O(n) 空间复杂度 O(1)
5. 分摊复杂度 (分摊分析法)对比 递增式扩容 << 加倍式扩容 (空间换时间)
装填因子=实际所用容量/最大容量。
- 平均分析法 & 分摊分析法
此处已要求 r< size 如果在实际中需要更为严格的处理
vector [] 重载
- 插入操作 有可能会overflow 所以需要判断是否扩容
- 删除操作 shrink 非必要 往往可以省略
- 查找 O(n)
输入敏感： 最好与最坏的时间复杂度相差悬殊
- 唯一化 去重 :保证 i 的前面的数都是互异的
- 优化 排序 + 二分
- 遍历 全局的通用性更强
感觉可以用二分 查找左右边界进行计算
迭代版本：
