算法与数据结构基础：复杂度分析与线性表

第1章 复杂度分析基础

任何算法都运行在有限的资源之上——时间是计算量，空间是内存占用。复杂度分析帮助我们预先评估算法的效率，而无需实际运行代码。

1.1 为什么需要复杂度分析

编写程序时，同一个问题往往有多种解法。例如排序，可以用冒泡排序、快速排序等。如果没有科学的度量方法，只能凭感觉判断孰优孰劣。依赖运行时间测试存在严重缺陷：

• 受硬件环境影响：不同机器执行速度不同。
• 与数据规模强相关：小数据量无法暴露低效算法的问题。
• 难以预估极限：当数据量增长到千万级时，某些算法的运行时间可能从秒级变成天级。

复杂度分析用数学方式描述算法执行时间（或占用空间）随输入规模增长的变化趋势，从而给出独立于机器的效率评估。

1.2 时间复杂度与大 O 表示法

时间复杂度衡量的是算法执行时间的增长趋势，记作 T(n) = O(f(n))。其中：

• n 代表输入数据的规模。
• f(n) 是一个关于 n 的函数，表示基本操作执行次数的上限。
• O 表示处于同一数量级，忽略常数系数和低阶项。

我们只关心增长最快的部分，因为当 n 足够大时，它主导了整个算法的开销。

常见时间复杂度（由快到慢）：

• O(1) – 常数阶：执行时间不随数据规模变化，如通过索引访问数组元素。
• O(log n) – 对数阶：每次将问题规模缩小，如二分查找。
• O(n) – 线性阶：执行时间与数据规模成正比，如遍历数组求和。
• O(n log n) – 线性对数阶：高效的排序算法（快速排序、归并排序）通常属于此级别。
• O(n²) – 平方阶：嵌套循环处理数据，如冒泡排序、简单矩阵乘法。
• O(2ⁿ) – 指数阶：暴力穷举组合问题，n 稍大即无法使用。
• O(n!) – 阶乘阶：典型的极端情况，如旅行商问题的暴力解法。

如何分析一段代码的时间复杂度？

1. 找出执行次数最多的语句，将其执行次数表示为 n 的函数。
2. 关注循环结构：单层循环通常为 O(n)，嵌套循环求乘积。
3. 忽略常数项、低阶项和系数，仅保留最高阶项。

举例：

// 求数组前n个元素之和
int sum(int arr[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += arr[i];
    }
    return total;
}

循环体执行 n 次，因此时间复杂度为 O(n)。

再看下面这个：

for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
        // 常量时间操作
    }
}

内层循环执行次数为 n + (n-1) + ... + 1 = n(n+1)/2，最高阶项为 n²/2，忽略系数，复杂度为 O(n²)。

1.3 空间复杂度

空间复杂度描述算法运行过程中额外占用的存储空间的增长趋势，同样用大 O 表示法。这里的“额外”指的是除了输入数据本身所占用的空间之外，算法需要新开辟的内存。

• 若算法只使用有限几个临时变量（如交换、累加），则空间复杂度为 O(1)，称为原地工作。
• 若需要开辟一个与输入规模 n 成正比的辅助数组，则为 O(n)。
• 递归算法的空间复杂度还要考虑调用栈的深度。

例如，递归求斐波那契数列第 n 项的函数，其调用栈最深可达 n 层，因此空间复杂度为 O(n)。而使用循环迭代实现，仅需常数级别额外空间，即 O(1)。

1.4 复杂度分析的核心准则

• 关注最坏情况：通常以最坏时间复杂度作为算法的保证，它可以回答“至少需要多长时间”的可靠性问题。
• 平均情况更有实际指导意义，但分析难度较高。
• 不纠结小规模数据：常数项在小数据量时可能非常明显，但复杂度分析着眼于增长趋势。
• 额外空间也很重要：内存有限的场景（嵌入式、移动端）中，即使时间很快，空间消耗过大也可能导致程序崩溃。

第2章 线性表

线性表是最基本、最常用的一种数据结构。它是由 n 个数据元素组成的有限序列，每个元素有且仅有一个前驱和一个后继（第一个元素无前驱，最后一个元素无后继）。

2.1 线性表的抽象定义

从逻辑结构上看，线性表可以表示为：(a1, a2, a3, ..., an)。其基本操作应包括：

• 初始化：创建空的线性表。
• 求表长：返回当前元素个数。
• 按位置查找：获取第 i 个位置的元素。
• 按值查找：找到第一个与给定值相等的元素位置。
• 插入：在指定位置插入一个新元素。
• 删除：移除指定位置的元素并返回其值。

根据存储方式不同，线性表主要分为顺序表和链表两种实现。

2.2 顺序表 —— 内存中的连续世界

顺序表用一组地址连续的存储单元依次存放线性表的数据元素，典型代表就是程序语言中的数组。

物理特征： 所有元素紧邻存放，可以通过 起始地址 + 偏移量 在 O(1) 时间内访问任意元素（随机存取）。

2.2.1 基本操作的实现与复杂度

• 查找（按位置）：直接通过数组下标访问，时间复杂度 O(1)。
• 查找（按值）：需要从第一个元素开始逐个比较，直到找到或遍历结束，平均情况需要检查 n/2 个元素，最坏为 n 次。时间复杂度 O(n)。
• 插入：在第 i 个位置插入新元素，需要将第 i 个到最后一个元素全部向后移动一位，平均移动 n/2 个元素。时间复杂度 O(n)。
• 删除：删除第 i 个位置元素后，需要将第 i+1 个到最后一个元素全部向前移动一位，平均移动 (n-1)/2 个元素。时间复杂度 O(n)。

因此，顺序表适合频繁读取、不常插入删除的场景。需要提前分配固定容量，当元素个数超出初始容量时，需要动态扩容——通常申请一块更大的连续内存，将原数据拷贝过去，这也会引入 O(n) 的时间开销。

2.3 链表 —— 指针串起的数据序列

链表用一组任意的存储单元（可以不连续）存储线性表元素，每个结点除了存放数据本身，还包括一个（或多个）指针，指向其逻辑上的后继（或前驱）结点。

2.3.1 单链表的结构

单链表的结点结构如下：

[ data | next ] → [ data | next ] → ... → NULL

• data 域存储数据值。
• next 域存放直接后继结点的地址。
• 最后一个结点的 next 指向 NULL。
• 单独维护一个头指针 head 指向第一个结点（若链表为空则为 NULL）。

2.3.2 带头结点的单链表

为了统一操作边界条件，经常引入一个不存储实际数据的头结点。此时 head 指针始终指向头结点，真正的数据从第二个结点开始。这样插入和删除第一个元素时无需特殊处理 head。

2.3.3 基本操作的实现与复杂度

• 按位置查找：必须从头结点（或第一个数据结点）开始，沿着 next 指针逐个向后移动，直到到达目标位置。时间复杂度 O(n)。
• 按值查找：同样需要遍历链表，最坏比较 n 次，O(n)。
• 插入结点：假设要在第 i 个位置插入新结点，需要先找到第 i-1 个结点。将新结点的 next 指向第 i-1 个结点的原后继，再将第 i-1 个结点的 next 更新为新结点。插入本身为 O(1)，但查找前驱结点需要 O(n) 时间，因此总复杂度仍是 O(n)。（若已知前驱结点的引用，则是 O(1)）。
• 删除结点：找到待删除结点的前驱，将其 next 指向待删除结点的后继，再释放待删除结点。同样，主要开销在于定位，总复杂度 O(n)。

链表的最大优势在于插入和删除不需要移动大量数据，只需修改指针；但它失去了随机存取能力，不能直接通过下标访问元素。

2.3.4 循环链表与双向链表

• 循环链表：将单链表尾结点的 next 由 NULL 改为指向头结点（或第一个数据结点）。从任意结点出发都能找到其他结点。
• 双向链表：每个结点除了 next 指向后继，还增加 prev 指向前驱。这使得反向遍历和删除操作更加方便（可以直接通过目标结点自身找到前驱）。其空间开销略大，但某些操作更高效。

2.4 顺序表与链表的选择

选择建议：

• 若操作以随机访问为主、尾部插入较多，优先考虑顺序表（或动态数组）。
• 若需要频繁在中间位置插入删除，且数据量较大，链表更合适。
• 内存空间无法保证连续大块分配时，链表是更好的选择。
• 实际开发中，高级语言的 list、ArrayList 等底层通常是动态数组，而 LinkedList 则是双向链表实现，可参考上述特性选用。

2.5 线性表的代码实现示例（C语言风格）

顺序表动态实现骨架

#define INIT_CAPACITY 10

typedef struct {
    int *data;      // 存储空间基址
    int length;     // 当前长度
    int capacity;   // 当前分配的容量
} SeqList;

// 初始化
void initList(SeqList *L) {
    L->data = (int*)malloc(INIT_CAPACITY * sizeof(int));
    L->length = 0;
    L->capacity = INIT_CAPACITY;
}

// 插入（第i个位置，i从1开始）
int insert(SeqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return 0;
    // 扩容逻辑忽略
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j-1];
    L->data[i-1] = e;
    L->length++;
    return 1;
}

单链表（带头结点）骨架

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 初始化
void initList(LinkList *L) {
    *L = (LNode*)malloc(sizeof(LNode));
    (*L)->next = NULL;
}

// 头插法建立链表
void createHead(LinkList L, int a[], int n) {
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}

掌握复杂度分析与线性表，你就拥有了评价算法效率和实现基础数据结构的能力，这是深入算法世界的必要根基。