Lin's Notes Garden

DSA-01-Vector

课件的总结见: https://paste.ubuntu.com/p/vncMHvZHtX/

1. 抽象数据类型 (ADT) vs. 数据结构 (Data Structure)

  • ADT:
    • 是一个数学模型, 由其定义的数据和在该数据上的一组操作构成.
    • 关注 "做什么" (What): 定义了操作及其逻辑属性 (语义) , 相当于一个接口.
    • 抽象性: 隐藏内部表示和实现细节.
    • 关注点: 逻辑特性、操作及语义.
    • 忽略: 具体实现、编程语言、时空效率、存储方式.
  • 数据结构:
    • 是 ADT 的一个具体实现, 提供了执行 ADT 操作的算法集合.
    • 关注 "如何做" (How): 数据如何组织, 操作如何执行.
    • 具体性: 涉及内部表示、具体算法、存储机制 (内存布局) 、时间和空间复杂度.
    • 关系: 一个 ADT 可以有多种数据结构实现.
  • 核心思想: 通过接口 (ADT) 将 "使用" (应用) 与 "实现" (数据结构) 分离, 带来模块化、可重用性、可维护性等好处.

2. 数组 (Array)

  • 定义: 元素存储在连续内存区域的集合.
  • 访问: 通过秩 (Rank) 或索引 (Index) 进行访问 (它们是同一个概念).
  • 核心特性: 直接访问 (Random Access). 任何元素 A[i] 的地址可通过基地址和元素大小计算得出 (BaseAddress + i * ElementSize).
  • 效率: 访问任意元素的时间复杂度为 O(1).

3. 向量 (Vector / Dynamic Array)

  • 概念: 作为数组的抽象和泛化, 封装了线性存储的元素序列. 通常基于底层数组实现.
  • 秩 (Rank): 每个元素对应一个唯一的秩 r (通常从 0 开始) , 是基本访问方式.
  • 核心挑战: 如何在不预知所需空间的情况下管理存储容量.

4. 动态空间管理 (Vector Resizing)

  • 问题: 固定容量数组可能导致溢出 (空间不足) 或利用率低 (空间浪费) .
  • 策略: 当向量满时 (size == capacity) , 进行扩容:
    1. 分配一个更大的新内存空间.
    2. 将旧空间中的元素复制到新空间.
    3. 释放旧空间.
  • 扩容因子与效率 (Amortized Analysis):
    • 按固定增量扩容: 每次增加固定大小 I. n 次插入的总复制成本约为 O(n^2). 分摊 (Amortized) 成本为 O(n) / 次插入. 效率低下.
    • 按比例 (如加倍) 扩容: 每次容量翻倍. n 次插入的总复制成本约为 O(n). 分摊 (Amortized) 成本为 O(1) / 次插入. 效率高, 是常用策略.
  • 分摊分析 (Amortized Analysis): 分析一系列操作的平均成本, 即使单次操作可能很昂贵. 适用于偶尔昂贵操作为后续多次廉价操作创造条件的情况 (如向量扩容) . 它不依赖概率, 提供序列操作的性能保证.

5. 向量基本操作 (无序向量)

  • 访问 (get/put 或 []): O(1).
  • 插入 (insert(r, e)):
    • 可能触发扩容 (分摊 O(1)) .
    • 需要将 r 及之后的所有元素向后移动一位.
    • 时间复杂度: O(n-r), 最坏情况 O(n) (插入到开头). 最好情况 (末尾插入) 分摊 O(1).
  • 删除 (remove(r) / remove(lo, hi)):
    • 需要将删除区间之后的所有元素向前移动.
    • 时间复杂度: O(n - (r+1)) 或 O(n - hi), 最坏情况 O(n) (从开头删除).
    • 区间删除通过单次移动实现比多次单元素删除更高效.
  • 查找 (find(e) - 无序):
    • 顺序查找 (Linear Search): 逐个比较元素.
    • 时间复杂度: 最坏/平均 O(n). 最好 O(1).
  • 去重 (dedup - 无序):
    • 移除所有重复元素, 通常保留第一个出现的.
    • 常用方法: 对每个元素 A[i], 查找它是否在 A[0, i) 中出现过, 若出现则删除 A[i].
    • 时间复杂度: 通常为 O(n^2).
  • 遍历 (traverse):
    • 对每个元素应用一个给定的操作 (visit) .
    • 时间复杂度: O(n) + n * T(visit), 其中 T(visit) 是单次访问操作的复杂度.

6. 有序向量操作

  • 有序性: 满足 A[i-1] <= A[i] (或 <, 取决于定义).
  • 唯一化 (uniquify - 有序):
    • 移除相邻的重复元素.
    • 低效方法: 比较相邻元素, 若相同则调用 remove. 因 remove 涉及移动, 最坏复杂度 O(n^2).
    • 高效方法 (双指针): 使用读指针 j 扫描, 写指针 i 记录唯一元素末尾. 仅当 A[j] != A[i] 时, 才将 A[j] 复制到 A[++i]. 单次遍历完成.
    • 时间复杂度: O(n).
  • 查找 (search(e) - 有序): 利用有序性加速查找.
    • 减而治之 (Reduce and Conquer): 通过与中间元素 ( "轴点" Pivot) 比较, 将搜索范围缩小.
    • 二分查找 (Binary Search):
      • 核心思想: 每次选取中间秩 mi = (lo + hi) / 2 作为轴点比较, 将搜索区间大小减半.
      • 时间复杂度: O(log n).
      • 不同版本: 主要区别在于比较策略 (三分支 vs 二分支) 和返回值语义.
      • 版本 C (推荐): 采用二分支比较 (e < S[mi] ? hi = mi : lo = mi + 1), 循环结束后 lo - 1 总是返回不大于 e 的最大元素的秩, 无论 e 是否存在, 提供了清晰的失败信息和插入点指示.
    • 斐波那契查找 (Fibonacci Search):
      • 核心思想: 使用斐波那契数分割查找区间 (分割成的两部分的长度之比近似于斐波那契数列中相邻两个数的比值), 试图使递归两侧的代价更均衡 (理论上比较次数的期望值略优于朴素二分) . 仅需加减法.
      • 时间复杂度: O(log n), 具有理论上最优的比较次数常数因子.
    • 插值查找 (Interpolation Search):
      • 核心思想: 假设数据均匀分布, 根据目标值 e 在 A[lo] 和 A[hi] 之间的相对位置来估计其秩 mi, 而不是简单取中点.
      • 时间复杂度:
        • 平均 (均匀数据): O(log log n).
        • 最坏 (非均匀数据): O(n).
      • 实用性: 适用于数据分布较均匀的情况, 常用于混合策略 (大范围插值, 小范围二分) .

7. 排序 (Sorting)

  • 稳定性 (Stability): 如果排序前后具有相同关键字的元素保持其原始相对顺序, 则排序算法是稳定的.
  • 起泡排序 (Bubble Sort):
    • 核心思想: 重复遍历序列, 比较并交换相邻的逆序元素, 使最大 (或最小) 元素逐渐 "冒泡" 到序列末端.
    • 时间复杂度:
      • 最坏/平均: O(n^2).
      • 最好 (已排序, 带优化标记): O(n).
    • 空间复杂度: O(1).
    • 稳定性: 稳定 (当比较用 < 或 > 时).
  • 归并排序 (Merge Sort):
    • 核心思想: 分治法 (Divide and Conquer).
      1. 分解: 将序列递归地对半分成子序列, 直到子序列长度为 1.
      2. 合并: 将两个已排序的子序列合并成一个有序序列.
    • 合并操作: 需要 O(n) 时间和 O(n) 辅助空间 (标准实现) . 通过比较两个子序列的当前元素, 将较小者放入结果序列. 使用 <= 保证稳定性.
    • 时间复杂度: O(n log n) (所有情况: 最坏、平均、最好).
    • 空间复杂度: O(n) (用于合并的辅助空间).
    • 稳定性: 稳定.
    • 优点: 时间复杂度稳定, 适合链表、外部排序.
    • 缺点: 非原地排序.

8. 位图 (Bitmap)

  • 概念: 使用一个比特位 (bit) 来表示一个整数是否存在于某个有限的全集 [0, U) 中.
  • 实现: 使用一个比特数组 (通常底层是字节数组 unsigned char M[]) . 整数 k 对应于字节 M[k >> 3] 中的第 k & 0x07 位.
  • 操作 (test(k), set(k), clear(k)): 通过位运算 (AND &, OR |, NOT ~, SHIFT >>) 在对应字节上操作特定位的掩码 (Mask).
  • 时间复杂度: O(1) / 操作.
  • 空间复杂度: O(U) 比特位, 即 O(U/8) 字节. 当集合相对于 U 较密集, 或 U 不太大时, 空间效率极高.
  • 应用:
    • 大数据去重 (N >> U): 用 Bitmap 记录 [0, U) 中出现的数. 时间 O(N+U), 空间 O(U).
    • 素数筛 (Sieve of Eratosthenes): 用 Bitmap 标记 [0, U) 中的合数. 时间 O(U log log U), 空间 O(U).
  • 快速初始化 (O(1) per operation cost):
    • 问题: 标准 Bitmap 初始化需要 O(U) 时间清零 (memset 时间复杂度为 O(n)).
    • 解决方案 (Hopcroft): 使用未初始化的 Bitmap B, 以及两个辅助数组 F (From), T (To) 和一个栈顶指针 top. T 存储实际设置过的元素, F 存储 k 在 T 中的位置. 通过 T[F[k]] == k 和 F[k] < top 来验证 k 是否有效存在.
    • 效果: set, clear, test, reset 操作的时间复杂度均为 O(1), 避免了 O(U) 的初始化开销.

Graph View

Backlinks