无序向量

无序向量

Insert & Remove

插入：自后向前地后移 删除：自前向后地前移

性能分析

• G：区间插入/删除

• S：单个元素插入/删除

• G2S：时间成本只取决于后缀长度，$O(n)$

• S2G：后缀多次小步前移，$O(n^2)$

• ! 重复性任务尽可能集中起来批量完成！

Expand

• 装填因子 $\lambda =size/capacity$
• 始终保持 $25\%\le \lambda \le 100\%$
• ~ 每次扩容容量翻倍
• 性能：最好 $O(1)$，最坏 $O(n)$

均摊分析

• 平均复杂度：根据各种操作出现的概率，对其运行时间做加权平均
• 均摊复杂度：考虑一个算法连续的、足够多次的调用，记录总时间，均摊给单次操作

性能分析

假设逐个插入 $n=2^m-1$ 个元素，最好情况不超过 $n$ 次，最坏情况不超过 $m$ 次，均摊至每一次调用，均摊复杂度只有 $O(1)$。

Find & Dedup

• 查找：顺序查找，最好 $O(1)$，最坏 $O(n)$，输入敏感
• 去重：减治，从前往后迭代，分为已经去重的前缀和待去重的后缀，对于每个迭代到的元素，查找需 $O(i)$，删除需 $O(n-i)$，总复杂度为 $O(n^2)$