（c）无序向量

官官方信息技术老师·11 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （c）无序向量信息技术（c）无序向量概述

无序向量ADT接口查找复杂度

（c）无序向量

理清无序向量的 ADT 接口语义、查找代价与顺序无关的操作边界

按空格/→ 演示下一步

1 / 11 页

全部页面点击任意一页，跳回舞台从这页播放

无序向量ADT接口查找复杂度

（c）无序向量

理清无序向量的 ADT 接口语义、查找代价与顺序无关的操作边界

1第 1 页 · （c）无序向量

概述

上一节点了'无序向量'这个名字。它和常见的词向量、位置编码有什么本质不同？这一页先把轮廓勾出来——是什么、关键性质、典型用法。

定义

维度互换不改变语义的向量；只关心'装了什么、各多少'

置换不变性

任意重排维度后，下游任务的结果保持等价

对比有序向量

词向量、位置编码中每个维度有专属含义，顺序错意思就变

典型应用

ColBERT 多向量检索、集合编码、BoW 嵌入

一袋混合水果对应 →无序向量

把苹果、香蕉、橘子混装一袋，怎么倒怎么摇，集合不变；只看'有什么、各多少'

f(\pi(\mathbf{x})) = f(\mathbf{x})

2第 2 页 · 概述

: 循秩访问

无序向量内部元素没有按关键码排序，要找到某个元素，最直接的办法就是「按位置数」——这正是循秩访问的思路。

秩即下标

向量中每个元素都有从 0 开始的编号，就是它的秩

唯一定位方式

无序向量没有大小次序，只能通过秩来定位元素

常数时间

秩对应物理地址偏移，访问时间为 O(1)

可读可写

通过秩既可取值，也可赋值修改，支持就地操作

典型应用

遍历、排序、查找等算法都建立在循秩访问之上

电影院排队取号对应 →循秩访问

叫到几号就服务几号——直接按编号找人，不问其他信息

3第 3 页 · : 循秩访问

插入

循秩访问让我们 O(1) 找到第 r 个元素；想扩大规模，就得靠插入：在秩 r 处安插新元素 e，原来的第 r 个变成第 r+1 个，其他元素依次后移一格。

操作签名

insert(r, e)：在秩 r 处插入新元素 e，原 [r, n) 区间整体后移一格

后移算法

从末元素 vec[n-1] 起倒着逐个右移一格，避免被覆盖

时间复杂度

平均 O(n)，需移动 n-r 个元素；尾插最佳 O(1)，头插最差 O(n)

秩的有效区间

r ∈ [0, n]，n 是当前规模，越界即非法

插入前判满

若 size == capacity 需先扩容（通常 2 倍）再写入

排队时有人插到第 r 位对应 →向量插入

新人站到位置 r，原本在那及后面的人依次后退一格，队伍变长

4第 4 页 · 插入

区间删除

单元素删除不过是「区间删除」的退化——只要把秩区间缩成 [r, r+1)。但批量清除过期记录、截取日志片段时，真正上场的就是区间删除。这页把它的代价与边界讲透。

操作语义

删除秩区间 [lo, hi)，长度缩减 hi - lo

后段前移

[hi, n) 元素依次迁至 lo+(i-hi)，再缩减 _size

代价分析

O(n - hi) 次复制；尾端 O(1)，首端 O(n)

单删的退化

remove(r) ≡ remove(r, r+1)，区间删除更具一般性

稿纸划掉一段对应 →区间删除

划掉后把后面整段往前抄补齐缺口，而不是留空

\forall\, i \in [hi, n):\;\; A[\,lo + (i - hi)\,] \leftarrow A[i]

5第 5 页 · 区间删除

单元素删除

上一页的区间删除把 [lo, hi) 整段一锅端。如果区间长度退化为 1，就回到最朴素的场景：只删一个元素。这页拆开来看，看清里面那一步「搬家」。

操作接口

remove(r) 删除秩为 r 的元素，返回被删值

核心动作

[r+1, n) 内的元素依次前移一位填补空位

时间复杂度

O(n - r)，代价随删除位置而变

位置极端

删尾 O(1)，删头 O(n)；越靠后越便宜

排队时中间有人离队对应 →单元素删除的前移填补

人走后，他身后所有人依次向前一步把队形补齐

$T(r) = n - r$

6第 6 页 · 单元素删除

查找

前面讲了怎么插入、删除元素，但更多时候我们只是想确认某个值在不在——这就是查找。无序向量里元素位置没有规律可循，没有捷径，只能从首元素起逐个比对过去。

顺序查找

从首元素起依次与目标比对，相等即成功，否则继续向后

时间复杂度

最好O(1)，最坏与平均均为O(n)，集中在末尾或未命中

失败判定

必须遍历全部n个元素才能确认'不存在'，无任何捷径

哨兵优化

尾部预置哨兵(目标值)，省去i<n边界判断，常数耗时近乎减半

无序的代价

无法二分查找，只能顺序；这是与有序向量的本质鸿沟

书架上一摞乱堆的书对应 →无序向量的顺序查找

没有目录只能一本本翻到底；翻完都没找到就是'不存在'

T(n) = \frac{1+2+\cdots+n}{n} = \frac{n+1}{2} = O(n)

7第 7 页 · 查找

唯一化

前面我们学会了在线性时间内查找。现在问一个自然延伸：若同一个值在向量里反复出现，能不能把重复的全都去掉？

定义

将重复出现的元素去除，使每个值仅保留一份

高效策略 O(n)

外部哈希集合记录已见值；扫描时仅保留未出现过的

低效策略 O(n²)

对每个元素向后扫描并调用单元素删除去重

无序的好处

新元素可紧凑写向头部，最后一次截断，无需维护空位

门卫按名册放行对应 →哈希集合去重

名册记下已放行的名字（集合），后面重复名字直接拦下

8第 8 页 · 唯一化

遍历

查找、唯一化都暗用了遍历——把向量从头到尾过一遍。现在把它独立出来，作为最基础的操作。

遍历定义

依秩 0~n-1 依次访问每个元素，恰各一次

两种模式

visit 只读不改，traverse 可就地修改

函数对象传入

通过回调函数决定对每个元素做什么

复杂度下界

必须触碰全部 n 个元素，Θ(n) 不可避免

老师按花名册点名对应 →向量遍历

从头到尾一个不漏；对每个元素做什么由传入的函数决定

9第 9 页 · 遍历

本节要点

✓O(1) 访问换 O(n) 增删查，是无序向量的代价核心
✓消除顺序依赖就能向量化，把 O(n²) 压到 O(n)
✓唯一化是典范：双循环变前缀+后缀扫描
✓区间删除 O(n-m+1) 是通用范式，单点是其特例
✓工程上别忘缩容策略与稳定性等边界条件

延伸主题：有序向量的二分查找与排序代价缩容策略的摊还复杂度分析向量化思想在其它结构的迁移

10第 10 页 · 本节要点

课后思考

先自己想，再看参考答案。三问层层递进，检验你对无序向量的理解深度。

1无序向量号称'插入 O(1)、查找 O(n)'——这种不对称的设计，背后交换了什么？

参考答案用'查找慢'换来了'插入快'。查找少而插入频繁时,这种交换划算；反之就是亏本买卖。数据结构的本质就是权衡。

2若程序要'先插入 10 万条数据,再反复查找某值是否存在',无序向量还是好选择吗？为什么？

参考答案不是。每次查找都要扫一遍,最坏要比较 10 万次。应当改用有序向量加二分查找,查找降到 O(logn),约 17 次比较就够。

3为什么无序向量的'区间删除'后容量不变？这种设计何时会成为隐患？

参考答案被删除的空间只是'逻辑隐藏',可被后续插入原地复用,避免反复申请。但若历史容量远大于当前规模,会浪费内存——需主动申请更小的新数组并整体迁移来释放。

11第 11 页 · 课后思考