袋鼠知识库

主题

第一章 抽象、复杂度与内存模型 ​

1. 为什么数据结构必须从“抽象”开始 ​

很多初学者一提到数据结构，就会立刻想到数组、链表、栈、队列、树、图，好像这门课的任务只是把这些名词逐个记住。这个理解太浅。数据结构真正研究的是这样一个链条：现实问题里有哪些对象，这些对象之间存在什么关系，这些关系应当如何表示到内存中，程序要支持哪些操作，这些操作在时间和空间上分别要付出什么代价。

如果没有这个链条，学习就会退化成死记硬背。你可能记得“数组查找快”“链表插入快”，但一旦别人追问“为什么”“什么条件下成立”“代码里是怎么体现的”，就答不上来。数据结构课程的价值，恰恰就在于把“程序能跑”提升为“程序为什么这样组织才更合理”。

上面这条链路决定了本专题的写法。我们不是先看代码再猜原理，而是先讲抽象，再讲内存，再讲实现，最后再做复杂度比较。

2. 什么是数据结构 ​

数据结构可以理解为“带有组织关系的数据，以及作用在这些数据上的操作规则”。因此它至少包含两部分：

  1. 数据之间的关系。
  2. 对这些数据可执行的操作。

例如“学生成绩表”这个对象，如果只是孤零零的一堆数字，不构成数据结构；只有当我们关心这些数字按照什么顺序存储、如何按学号查找、如何插入新同学、如何统计排名时，它才进入数据结构的讨论范围。

更严格地说，数据结构并不是单纯描述“数据长什么样”，而是在回答“数据应该怎样组织，程序才能更高效地处理它”。这也是为什么数据结构和算法总是连在一起：结构决定操作边界，算法利用这些边界。

3. 抽象数据类型：先定义行为，再讨论实现 ​

学习数据结构时，必须先建立抽象数据类型（ADT, Abstract Data Type）的观念。ADT 关注的是“这个结构应该支持什么行为”，而不是“它在代码里具体怎么写”。

以栈为例，抽象层面只关心：

  1. Push(x)：把元素压入栈顶。
  2. Pop()：弹出栈顶元素。
  3. Peek()：读取栈顶元素但不删除。
  4. IsEmpty()：判断栈是否为空。

至于底层用数组实现，还是用链表实现，属于实现层问题。这个区分非常关键，因为它能帮助你理解：不同实现可以服务同一个抽象接口，而同一个实现思路也可能支撑多个抽象结构。

4. 数据结构研究的四个层面 ​

4.1 逻辑结构 ​

逻辑结构关心的是元素之间“概念上”的关系，而不是它们在内存里怎么摆放。常见逻辑结构包括：

  1. 线性结构：一个元素通常只有一个直接前驱和一个直接后继。
  2. 树形结构：一个元素可以派生多个下级元素，体现层次关系。
  3. 图结构：元素之间存在任意多对多连接。
  4. 集合结构：主要关心元素是否属于同一个集合，而不强调次序。

4.2 存储结构 ​

存储结构关心这些逻辑关系如何映射到物理内存。最常见的两类思想是：

  1. 连续存储：元素放在一段连续地址中，例如数组、切片底层数组、堆数组表示。
  2. 链式存储：元素分散在不同地址，通过指针或引用关联，例如链表、树节点、图的邻接表节点。

4.3 操作集合 ​

一个结构是否值得使用，取决于它支持哪些操作。例如：

  1. 按位置访问。
  2. 按关键字查找。
  3. 插入与删除。
  4. 求最值。
  5. 合并、拆分、遍历、判连通。

4.4 复杂度 ​

最终必须回到代价。一个结构如果理论上能完成任务，但完成一次要花 O(n^2)，而另一个只需 O(n log n)，它们在工程上的意义完全不同。

5. 时间复杂度：不是“运行时间”，而是增长规律 ​

时间复杂度研究的是：当输入规模 n 增长时，算法执行步骤数量如何增长。它不直接等于真实运行时间，因为真实时间还受机器、编译器、缓存、数据分布等影响；但它能提供最重要的上层规律。

常见复杂度层级如下：

复杂度直观含义典型例子
O(1)与规模无关的常数级开销数组按下标访问
O(log n)每步都把问题规模缩小一部分二分查找
O(n)扫描全部元素线性查找
O(n log n)分治或树形层次处理归并排序、堆排序
O(n^2)双重比较或双层扫描冒泡排序、简单选择排序

要特别注意三点：

  1. 复杂度描述的是数量级，不是精确秒数。
  2. 常数小的 O(n) 在小数据量下可能比常数大的 O(log n) 更快。
  3. 平均复杂度、最坏复杂度和均摊复杂度不是一回事。

6. 空间复杂度与额外空间 ​

空间复杂度描述的是算法随输入规模增长所额外占用的存储空间。要区分两类空间：

  1. 输入本身占用的空间。
  2. 为了完成运算而额外申请的辅助空间。

例如原地交换数组元素的排序，额外空间可能是 O(1)；归并排序需要辅助数组，通常是 O(n)；递归算法还要考虑调用栈深度。

7. 内存模型：为什么“连续”和“链接”会产生本质差异 ​

很多复杂度差异，最终都能在内存层面找到根源。

7.1 连续内存 ​

连续内存的优势是：

  1. 可以通过基地址加偏移量直接定位第 i 个元素。
  2. CPU 缓存友好，顺序扫描效率高。
  3. 结构简单，额外指针开销少。

代价是：

  1. 中间插入和删除可能引发搬移。
  2. 扩容时可能要申请新空间并整体复制。

7.2 链式内存 ​

链式存储的优势是：

  1. 插入和删除可以只改局部指针。
  2. 不要求元素在物理上连续。
  3. 适合动态生长和复杂关系建模。

代价是：

  1. 无法常数时间按位置随机访问。
  2. 指针额外占空间。
  3. 缓存局部性较差。

8. Go 语言中的内存视角 ​

这一专题统一使用 Go 写示例，但不要因为 Go 提供了切片、map、container/heap 等高级工具，就忽略底层原理。学习数据结构时，仍然要盯住三件事：

  1. 值语义还是引用语义。
  2. 底层数组是否可能扩容。
  3. 指针连接是否会造成共享状态。

下面这个例子体现了切片共享底层数组的现象：

go
package main

import "fmt"

func main() {
    a := []int{10, 20, 30, 40}
    b := a[1:3]
    b[0] = 99
    fmt.Println(a) // [10 99 30 40]
}

这说明切片不是“复制一份新数组”，而只是对原数组某个窗口的描述。后面学习动态数组、队列和堆时，这个事实非常重要。

9. 第一章必须建立的三条主线 ​

学完这一章，至少要把下面三条主线建立起来：

9.1 先问关系，再问实现 ​

不要一上来就问“我要不要用红黑树”。先问数据是线性的、层次的、网络化的，还是只关心集合归属。逻辑关系先于实现细节。

9.2 先问主操作，再问容器名字 ​

如果主操作是随机访问，数组和切片就天然有优势；如果主操作是频繁队头出队，普通数组就不够理想；如果要维护最小值，堆比排序后数组更合适。

9.3 复杂度结论必须能还原到内存原因 ​

“为什么数组访问是 O(1)”“为什么链表按下标访问是 O(n)”“为什么堆插入是 O(log n)”，都不应该只是记忆结论，而要能说出它们分别对应的内存定位方式和结构不变量。

10. 进入后续章节前，你应当会回答的问题 ​

  1. 什么是抽象数据类型，为什么它和具体实现要分开看？
  2. 逻辑结构和存储结构的区别是什么？
  3. 为什么连续存储通常擅长随机访问？
  4. 为什么链式结构通常擅长局部插删？
  5. 为什么复杂度分析必须和主操作结合，而不能脱离场景单独讨论？

后续所有章节，都会在这套框架上展开。