第1章：引论（Introduction）

一、导读

1.1 本章学习目标

第1章是《数据结构与算法分析：C语言描述》的开篇之作，它为整本书奠定了理论基础。本章的核心任务是建立算法分析的基本框架——你将学会如何衡量一个算法的"好坏"，如何用数学工具精确描述算法的效率，以及递归这一贯穿全书的重要编程技巧。在后续章节深入学习各种数据结构之前，掌握这些分析工具是至关重要的：因为没有度量的标准，就无法比较不同方案的优劣。

本章的核心学习目标包括：

理解算法的定义和特性：什么是一个算法？有限性、确定性、输入、输出、可行性这五个特性为什么缺一不可？
掌握大O表示法：如何用渐近记号描述算法的增长率？为什么我们只关注最高阶项而忽略常数因子？
学会分析时间复杂度：给定一段代码，如何系统地计算它的时间复杂度？嵌套循环、递归调用的分析方法有何不同？
理解递归的本质：递归的基线条件和递归条件是什么？递归如何与数学归纳法对应？
认识不同复杂度的差异：O(1)、O(log n)、O(n)、O(n²)、O(2ⁿ) 在实际运行中意味着什么？
掌握C语言的基本工具：指针、结构体、动态内存分配等后续章节频繁使用的C语言特性。

1.2 为什么第一章如此重要

很多初学者会急于跳过"引论"，觉得这些概念"太理论"或"太简单"。这种想法是极其危险的。正如建筑师必须理解力学原理，程序员也必须理解算法分析的基本方法。没有分析能力，你写出的代码可能"能跑"，但你无法判断它是否"够快"。

Weiss 在本章中反复强调一个核心观点：写程序不仅要正确，还要高效。一个正确的算法如果在合理时间内无法给出结果，那它就没有实用价值。算法分析为我们提供了一把"尺子"，让我们可以在编写代码之前就预估其性能，从而在众多可行方案中选择最优的那个。

此外，本章引入的递归思想将在后续几乎所有章节中出现——从树的遍历到分治算法，从快速排序到图的深度优先搜索。如果在这一章没有打好递归的基础，后续学习将会非常吃力。

1.3 核心问题引导

在阅读本章时，请带着以下问题思考：

当输入规模 n 增大10倍时，O(n) 和 O(n²) 的算法运行时间分别增大多少倍？

为什么我们说"一个运行时间为 O(n²) 的算法比 O(n log n) 的算法慢"时，这种说法在 n 很小时可能不成立？

递归函数如果忘记写基线条件会发生什么？如何保证递归一定能够终止？

斐波那契数列的递归实现为什么效率极低？如何将其优化为线性时间？

大O表示法描述的是"最坏情况"还是"所有情况"？它和"实际运行时间"有什么区别？

如何选择递归还是迭代来实现同一个问题？各有什么优缺点？

二、核心概念详解

2.1 什么是算法

算法（Algorithm） 是解决特定问题的一系列明确指令的有限集合。一个算法必须满足以下五个特性：

有限性（Finiteness）：算法必须在有限步之后终止。一个永远运行不停的过程不是算法。
确定性（Definiteness）：算法的每一步都必须有明确无歧义的定义。不能有"随便选一个"这样的模糊指令。
输入（Input）：算法有零个或多个外部输入。这些输入是从特定集合中取出的量。
输出（Output）：算法产生一个或多个输出。输出与输入之间存在特定的关系。
可行性（Effectiveness）：算法的每一步操作都必须是足够基本的，原则上可以在有限时间内由人用纸和笔完成。

// 一个合法的算法：求数组中的最大值
int findMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal)
            maxVal = arr[i];
    }
    return maxVal;
}
// 满足五个特性：
// 有限性：循环执行n-1次后终止
// 确定性：每步操作明确
// 输入：数组arr和长度n
// 输出：最大值maxVal
// 可行性：比较和赋值都是基本操作

2.2 大O表示法

大O表示法（Big-O Notation） 是描述函数增长率上界的数学工具。在算法分析中，它用于描述算法运行时间（或空间）随输入规模增长的趋势。

形式化定义：若存在正常数 c 和 n₀，使得对所有 n ≥ n₀，有 T(n) ≤ c·f(n)，则称 T(n) = O(f(n))。

直觉上理解，大O表示法告诉我们的是：当输入规模足够大时，算法的运行时间最多按 f(n) 的速度增长。它忽略常数因子和低阶项，因为我们关注的是"增长趋势"而非精确的运行时间。

2.2.1 常见复杂度等级

复杂度	名称	n=10	n=100	n=1000	n=10000
O(1)	常数时间	1	1	1	1
O(log n)	对数时间	~3	~7	~10	~13
O(n)	线性时间	10	100	1000	10000
O(n log n)	线性对数	~30	~700	~10000	~130000
O(n²)	平方时间	100	10000	10⁶	10⁸
O(n³)	立方时间	1000	10⁶	10⁹	10¹²
O(2ⁿ)	指数时间	1024	10³⁰	10³⁰¹	—

从表中可以清楚地看到：当 n 较大时，低复杂度算法的优势是压倒性的。O(n²) 的算法在 n=10000 时需要 10⁸ 次操作，而 O(n log n) 只需要约 130000 次——相差近 1000 倍。

2.2.2 大O的分析规则

分析代码的时间复杂度时，有几条基本规则：

// 规则1：单条语句是 O(1)
int x = 5;                    // O(1)

// 规则2：顺序结构取最大值
for (int i = 0; i < n; i++)   // O(n)
    printf("%d ", i);
int y = 10;                    // O(1)
// 总计：O(n) + O(1) = O(n)

// 规则3：循环结构 = 循环次数 × 循环体复杂度
for (int i = 0; i < n; i++)   // 执行n次
    for (int j = 0; j < n; j++) // 每次O(1)
        x++;
// 总计：O(n²)

// 规则4：嵌套循环从内到外分析
for (int i = 0; i < n; i++)         // 外层n次
    for (int j = i; j < n; j++)     // 内层n-i次
        for (int k = 0; k < j; k++) // 最内层j次
            x++;
// 总计：Σ(i=0 to n-1) Σ(j=i to n-1) j = O(n³)

// 规则5：if-else取较大分支
if (condition) {
    // O(n) 的操作
} else {
    // O(n²) 的操作
}
// 总计：O(n²)（取最坏分支）

2.2.3 常见误区

误区一：把所有循环次数相乘。并非所有嵌套循环都是 O(n²)。如果内层循环的次数与外层无关，才能直接相乘。

// 这是 O(n)，不是 O(n²)！
for (int i = 0; i < n; i++) {     // n次
    for (int j = 0; j < 10; j++) { // 常数次
        x++;
    }
}
// O(n) × O(1) = O(n)

// 这是 O(n log n)
for (int i = 1; i < n; i *= 2) { // log n次
    for (int j = 0; j < i; j++) { // i次，但...
        x++;
    }
}
// 总操作次数：1 + 2 + 4 + ... + n/2 ≈ 2n = O(n)

误区二：混淆大O和实际运行时间。大O描述的是增长趋势，不是精确时间。一个 O(n) 的算法在 n 很小时可能比 O(1) 的算法更慢（因为常数因子更大）。

2.3 递归基础

递归（Recursion） 是指函数直接或间接调用自身的编程技巧。递归的核心思想是将一个大问题分解为规模更小的同类子问题，直到子问题足够小可以直接求解。

每个递归函数都必须包含两个部分：

基线条件（Base Case）：不需要递归就能直接求解的简单情况。这是递归终止的条件。
递归条件（Recursive Case）：将问题分解为子问题并递归求解的部分。每次递归调用都必须使问题向基线条件靠近。

// 阶乘的递归实现
int factorial(int n) {
    if (n <= 1)           // 基线条件
        return 1;
    return n * factorial(n - 1);  // 递归条件
}
// factorial(5) = 5 * factorial(4)
//             = 5 * 4 * factorial(3)
//             = 5 * 4 * 3 * factorial(2)
//             = 5 * 4 * 3 * 2 * factorial(1)
//             = 5 * 4 * 3 * 2 * 1
//             = 120

// 斐波那契数列的递归实现 - 极其低效！
int fib(int n) {
    if (n <= 1) return n;    // 基线条件
    return fib(n - 1) + fib(n - 2);  // 递归条件
}
// 时间复杂度：O(2ⁿ) - 指数级！
// 原因：大量重复计算
// fib(5) 调用 fib(4) 和 fib(3)
// fib(4) 又调用 fib(3) 和 fib(2)
// fib(3) 被计算了两次！

// 迭代版本 - O(n)
int fib_iter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

2.3.1 递归的效率问题

递归虽然优雅，但并不意味着总是高效的。上面斐波那契的例子就说明了这一点：一个看似简洁的递归实现可能隐藏着指数级的时间复杂度。

递归的效率问题主要来自两方面：

重复计算：如斐波那契的例子，相同的子问题被反复求解。解决方法是"记忆化"（Memoization）——将已计算的结果保存起来。

函数调用开销：每次递归调用都需要在栈上分配空间保存参数、返回地址和局部变量。递归过深可能导致栈溢出。

// 记忆化版本的斐波那契 - O(n)
int memo[1000];

int fib_memo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // 已计算过，直接返回
    memo[n] = fib_memo(n - 1) + fib_mem(n - 2);
    return memo[n];
}
// 每个 fib(i) 只计算一次，总计 O(n)

2.4 C语言基础回顾

本书使用 C 语言作为实现语言。以下几个 C 语言特性在后续章节中会频繁使用：

2.4.1 指针与动态内存分配

#include <stdlib.h>
#include <stdio.h>

// 动态分配数组
int *arr = (int *)malloc(10 * sizeof(int));
if (arr == NULL) {
    fprintf(stderr, "Memory allocation failed\n");
    exit(1);
}
// 使用数组...
for (int i = 0; i < 10; i++)
    arr[i] = i * i;

// 释放内存（非常重要！）
free(arr);
arr = NULL;  // 防止悬空指针

// 动态分配结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *createNode(int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    newNode->data = val;
    newNode->next = NULL;
    return newNode;
}

2.4.2 结构体与类型定义

// 使用 typedef 简化类型声明
typedef struct {
    int x;
    int y;
} Point;

// 结构体数组
Point points[100];
points[0].x = 10;
points[0].y = 20;

// 结构体指针
Point *p = &points[0];
printf("(%d, %d)\n", p->x, p->y);

2.4.3 函数指针（回调函数）

// 比较函数类型
typedef int (*CompareFunc)(const void *, const void *);

// 整数比较函数
int compareInt(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 使用 qsort
int arr[] = {5, 2, 8, 1, 9, 3};
int n = 6;
qsort(arr, n, sizeof(int), compareInt);
// arr 现在是 {1, 2, 3, 5, 8, 9}

三、实战案例

3.1 最大子序列和问题

这是一个经典的算法分析问题。给定一个整数序列 A₁, A₂, ..., Aₙ，求最大的连续子序列之和。

#include <stdio.h>
#include <time.h>

// 算法1：暴力枚举 - O(n³)
int maxSubSum1(const int a[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int thisSum = 0;
            for (int k = i; k <= j; k++)
                thisSum += a[k];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    return maxSum;
}

// 算法2：改进的暴力 - O(n²)
int maxSubSum2(const int a[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int thisSum = 0;
        for (int j = i; j < n; j++) {
            thisSum += a[j];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
}

// 算法3：分治法 - O(n log n)
int maxSubSum3(const int a[], int left, int right) {
    if (left == right) {
        return a[left] > 0 ? a[left] : 0;
    }
    int center = (left + right) / 2;
    int maxLeftSum = maxSubSum3(a, left, center);
    int maxRightSum = maxSubSum3(a, center + 1, right);
    
    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= left; i--) {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++) {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    
    int max1 = maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
    int max2 = maxLeftBorderSum + maxRightBorderSum;
    return max1 > max2 ? max1 : max2;
}

// 算法4：Kadane算法 - O(n)
int maxSubSum4(const int a[], int n) {
    int maxSum = 0, thisSum = 0;
    for (int i = 0; i < n; i++) {
        thisSum += a[i];
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
    }
    return maxSum;
}

int main() {
    int a[] = {-2, 11, -4, 13, -5, 2};
    int n = 6;
    
    printf("Algorithm 1 (O(n³)): %d\n", maxSubSum1(a, n));
    printf("Algorithm 2 (O(n²)): %d\n", maxSubSum2(a, n));
    printf("Algorithm 3 (O(n log n)): %d\n", maxSubSum3(a, 0, n - 1));
    printf("Algorithm 4 (O(n)): %d\n", maxSubSum4(a, n));
    // 所有算法输出：20（子序列 11, -4, 13）
    return 0;
}

运行结果分析：

四个算法给出相同的结果 20，但效率天差地别。当 n 从 100 增加到 10000 时：

算法1 的操作次数从 10⁶ 增长到 10¹²（增加100万倍）
算法4 的操作次数从 100 增长到 10000（仅增加100倍）

Kadane 算法的精妙之处在于：当 thisSum 变为负数时，它不可能对后续的和产生正贡献，因此将其重置为 0。这个 O(n) 的算法是"在线"的——只需扫描一遍数据。

3.2 验证不同复杂度的实际运行时间

#include <stdio.h>
#include <time.h>

// O(n) 算法
void linear(int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += i;
}

// O(n²) 算法
void quadratic(int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum += i * j;
}

// O(n³) 算法
void cubic(int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                sum += i * j * k;
}

int main() {
    int sizes[] = {100, 500, 1000, 2000, 5000};
    
    printf("%-8s %-12s %-12s %-12s\n", "n", "O(n)", "O(n²)", "O(n³)");
    printf("----------------------------------------------\n");
    
    for (int s = 0; s < 5; s++) {
        int n = sizes[s];
        clock_t start, end;
        
        start = clock();
        linear(n);
        end = clock();
        double t1 = (double)(end - start) / CLOCKS_PER_SEC;
        
        start = clock();
        quadratic(n);
        end = clock();
        double t2 = (double)(end - start) / CLOCKS_PER_SEC;
        
        start = clock();
        cubic(n);
        end = clock();
        double t3 = (double)(end - start) / CLOCKS_PER_SEC;
        
        printf("%-8d %-12.6f %-12.6f %-12.6f\n", n, t1, t2, t3);
    }
    return 0;
}

输出示例：

n        O(n)         O(n²)        O(n³)       
----------------------------------------------
100      0.000001     0.000030     0.001200    
500      0.000003     0.000700     0.075000    
1000     0.000005     0.002800     0.600000    
2000     0.000010     0.011000     4.800000    
5000     0.000025     0.069000     75.000000

从数据中可以清楚地看到：

O(n) 的增长几乎可以忽略
O(n²) 在 n=5000 时已经需要 0.069 秒
O(n³) 在 n=5000 时需要 75 秒——比 n=1000 时慢了约 125 倍（5³ = 125）

这直观地验证了理论分析的正确性。

四、本章小结

第1章为整本书建立了分析基础，核心要点如下：

算法分析是评估算法效率的数学工具。我们使用大O表示法来描述算法运行时间随输入规模增长的趋势，忽略常数因子和低阶项。

常见复杂度从低到高排列为：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)。当输入规模较大时，低复杂度算法具有压倒性优势。

递归是将问题分解为同类子问题的编程技巧。每个递归函数必须有基线条件和递归条件，且每次递归必须使问题向基线条件靠近。

分析代码复杂度的基本规则包括：顺序结构取最大值、循环结构等于循环次数乘以循环体复杂度、嵌套循环从内到外逐层分析。

算法选择对性能的影响是决定性的。同一个问题（如最大子序列和），不同复杂度的算法在实际运行时间上可能相差数百万倍。

本章最重要的启示是：在写代码之前先分析复杂度。一个好的程序员不仅要知道代码"能不能跑"，更要知道"跑得够不够快"。当输入规模从 100 增长到 100 万时，O(n) 和 O(n²) 的差距将从微不足道变为天壤之别。

五、思考与练习

思考题

如果一个算法的运行时间是 O(n log n)，当输入规模增大 8 倍时，运行时间大约增大多少倍？（提示：不是简单的 8 倍）

考虑以下代码片段，它的时间复杂度是什么？

for (int i = 1; i < n; i *= 2) {
    for (int j = 0; j < i; j++) {
        // O(1) 操作
    }
}

为什么我们通常用大O表示法描述"最坏情况"而不是"平均情况"？平均情况分析有什么困难？

递归和迭代在本质上是可以互相转换的。那么在实际编程中，什么时候应该选择递归，什么时候应该选择迭代？

编程练习

对数复杂度：编写一个 O(log n) 的函数，计算 x 的 n 次幂（xⁿ）。提示：利用 xⁿ = (x²)^(n/2) 的递归关系。

递归分析：分析以下递归函数的时间复杂度，并给出数学证明：

void mystery(int n) {
    if (n <= 0) return;
    for (int i = 0; i < n; i++)
        printf("*");
    mystery(n - 1);
}

最大子序列和：修改 Kadane 算法，使其能够处理全为负数的数组（返回最大的负数而非 0）。