第 1 讲 · 数据结构与算法复杂度

数据结构不是“把几种结构的代码背下来”，而是研究三件彼此相连的事：数据之间有什么关系、这些关系怎样存进计算机、在这种存法上如何完成操作。

从数据到数据结构

数据是能够被计算机识别和处理的信息。
数据元素是讨论中的基本单位，例如学生表中的一名学生。
数据项是元素内部不可再分的字段，例如学号和姓名。
数据对象是性质相同的数据元素的集合。

数据结构可以写成三元组：数据元素集合 $D$ 、元素间关系集合 $R$ 、定义在这些数据上的操作集合 $P$ 。只谈“元素是什么”而不谈关系和操作，不能确定应采用什么结构。

逻辑结构：先问元素怎样关联

集合结构：元素同属一个集合，彼此没有额外次序。
线性结构：除首尾外，每个元素恰有一个直接前驱和一个直接后继。
树结构：一个元素可以对应多个后继，是一对多关系。
图结构：元素之间可以任意关联，是多对多关系。

逻辑结构与编程语言无关。课程中的线性表、栈、队列、树、图，首先都是这种抽象关系。

存储结构：关系怎样落到内存里

顺序存储

元素放在一片连续地址中，逻辑次序由物理次序直接表达。若每个元素占 $L$ 个存储单元，第一个元素地址为 $LOC(a_1)$ ，则

LOC(a_i)=LOC(a_1)+(i-1)L.

优点是随机访问快；缺点是中间插入、删除通常要移动元素，而且容量往往需要预先规划。

链式存储

元素可以分散存放，结点额外保存指向相关结点的指针。它用空间换灵活性：已知插入位置时只需修改少量指针，但按序号找第 $i$ 个元素必须沿链接逐个走。

索引和散列

索引另外保存“关键字到位置”的目录；散列通过函数直接把关键字映射到地址。两者都希望减少查找范围，但要付出额外空间和维护成本。

抽象数据类型

抽象数据类型只规定“有哪些数据、允许哪些操作、每个操作应产生什么结果”，不规定具体代码。例如栈只承诺 push、pop、取栈顶和判空；它可以用数组实现，也可以用链表实现。

这个分层很实用：先按问题选择抽象结构，再根据容量、访问模式和性能要求选择实现。

什么是算法

算法是解决一类问题的有限步骤。课件强调五个基本特征：

有穷性：有限步内结束；
确定性：每一步含义清楚；
可行性：每一步可以实际执行；
有零个或多个输入；
有一个或多个输出。

正确性只是底线。实际还要看可读性、健壮性，以及时间和空间效率。

时间复杂度不是“跑了多少秒”

机器、编译器和输入数据都会影响真实时间。算法分析改为统计基本操作随问题规模 $n$ 增长的数量级，并忽略常数和低阶项。

for (int i = 0; i < n; i++)
    sum += a[i];

循环体执行 $n$ 次，所以是 $O(n)$ 。

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        count++;

内层对每个 i 都执行 $n$ 次，总次数为 $n^2$ ，所以是 $O(n^2)$ 。

for (int x = 1; x < n; x *= 2)
    count++;

执行 $k$ 次后 $x=2^k$ ，当 $2^k\ge n$ 时结束，所以 $k=O(\log n)$ 。

常见增长速度为

O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)<O(n!).

最好、最坏和平均情况

同一算法在不同输入上可能走不同路径。顺序查找第一个元素只比较一次，查找失败却要看完整张表。课程中通常优先分析最坏情况，因为它给出性能上界；平均情况还需要知道输入的概率分布。

空间复杂度

空间复杂度关注除输入本身外的额外空间。原地交换只需常数变量，是 $O(1)$ ；归并排序需要与输入同量级的辅助数组，是 $O(n)$ ；递归还必须计算调用栈，每深入一层就保存一份现场。

用不变量理解算法

不变量是算法执行过程中始终成立的性质。例如插入排序第 $i$ 趟开始前，前 $i$ 个元素已经有序。每一趟只需要把下一个元素插入到正确位置，并重新建立这个性质。

以后看到任何算法，都可以依次问：

输入和输出是什么？
数据采用什么结构？
循环或递归每一步保持什么性质？
问题规模怎样缩小？
基本操作一共执行多少次？

这五问比背代码更可靠。