第1章 数据结构概述：三要素与算法效率度量

各位同学好，我是你们这门课的老朋友。今天咱们来聊聊数据结构的核心骨架——三要素，以及怎么衡量一个算法的好坏。这些东西听起来有点抽象，但说白了，就是程序员吃饭的家伙。

1.1 数据结构三要素

我刚开始学数据结构时，总觉得这玩意儿就是「数组、链表、树」这些具体的东西。后来踩了不少坑才明白，数据结构其实有三个层次：逻辑结构、存储结构、数据运算。这三者缺一不可。

1.1.1 逻辑结构

逻辑结构，就是数据元素之间的关系。你想想看，一堆数字放在那里，它们之间是什么关系？是前后挨着（线性），还是父子关系（树形），还是乱七八糟互相连接（图形）？

我个人习惯把逻辑结构分成四类：

• 集合：元素之间「没关系」，就是一堆东西放一起。比如一个班级的学生名单。
• 线性结构：元素之间「一对一」关系。比如排队买奶茶，每个人前面只有一个人，后面也只有一个人。
• 树形结构：元素之间「一对多」关系。比如公司的组织架构，一个老板管好几个经理。
• 图形结构：元素之间「多对多」关系。比如地铁线路图，一个站可以连好几个站。

1.1.2 存储结构

存储结构，说白了就是数据在内存里怎么放。主要有两种：

• 顺序存储：用一块连续的内存空间。数组就是典型例子。优点是随机访问快，缺点是插入删除麻烦。
• 链式存储：用不连续的内存空间，通过指针连起来。链表就是典型例子。优点是插入删除方便，缺点是不能随机访问。

嗯，这里要注意：同一个逻辑结构可以用不同的存储结构来实现。比如「栈」这个逻辑结构，既可以用数组实现（顺序栈），也可以用链表实现（链栈）。

1.1.3 数据运算

数据运算，就是你对数据能干什么。比如插入、删除、查找、排序、遍历等等。不同的逻辑结构，支持的运算也不一样。

我曾经在一个项目中，需要频繁地在中间插入数据。当时我用了数组，结果每次插入都要移动大量元素，性能惨不忍睹。后来改成链表，问题就解决了。这就是「数据运算」决定了你该选什么结构。

1.2 算法效率度量

写程序，光能跑通不行，还得跑得快、省内存。怎么衡量？两个指标：时间复杂度和空间复杂度。

1.2.1 时间复杂度

时间复杂度，不是真的去计时（那跟机器性能有关），而是看基本操作执行的次数跟数据规模 n 之间的关系。

举个例子：

// 代码1：查找数组中的最大值
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

这个循环执行了 n-1 次比较操作。所以时间复杂度是 O(n)。

// 代码2：冒泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

这个双层循环，比较次数大约是 n²/2 次。所以时间复杂度是 O(n²)。

1.2.2 空间复杂度

空间复杂度，就是算法运行时额外占用的内存。注意是「额外」，输入数据本身占的空间不算。

比如上面的冒泡排序，只用了几个临时变量（i, j, temp），跟 n 无关。所以空间复杂度是 O(1)。

但如果你写了一个递归函数，每递归一次就压一次栈，那空间复杂度可能就变成 O(n) 了。

1.3 大O表示法详解

大O表示法，说白了就是忽略常数和低阶项，只看增长趋势。为什么？因为当 n 很大时，常数和低阶项的影响可以忽略不计。

常见的复杂度从快到慢：

大O表示	名称	例子
O(1)	常数阶	数组随机访问
O(log n)	对数阶	二分查找
O(n)	线性阶	遍历数组
O(n log n)	线性对数阶	归并排序
O(n²)	平方阶	冒泡排序
O(2ⁿ)	指数阶	递归斐波那契

我建议你记住一个原则：O(1) 最好，O(n) 还行，O(n²) 要小心，O(2ⁿ) 基本别用。

为什么会这样？你想想看，当 n=100 时，O(n²) 要执行 10000 次，还能接受。但当 n=1000 时，O(n²) 就是 100 万次，开始卡了。而 O(2ⁿ) 在 n=30 时就已经是 10 亿次了，基本跑不动。

1.4 知识体系总览

下面这张图，把本章的核心内容串起来了。我建议你多看几遍，脑子里形成框架。

好了，这一章的内容就到这里。数据结构三要素和算法效率度量，是后面所有章节的基础。你想想看，如果连「逻辑结构」和「存储结构」都分不清，后面学链表、树、图的时候肯定会晕。所以，先把这些概念吃透，后面就顺了。

---