第1章：基础（Fundamentals）

一、导读

1.1 本章学习目标

第1章是《算法（第4版）》的基础篇，它为整个算法学习奠定方法论基础。算法分析是计算机科学的核心技能，而本章将教你如何进行这种分析。本章的核心学习目标包括：

理解算法的定义和基本特性：什么是算法？一个良好的算法应该满足什么条件？
掌握时间复杂度分析方法：如何使用大O表示法描述算法的增长率？
理解空间复杂度的概念：如何分析算法的内存使用？
掌握数据抽象的思想：如何设计抽象数据类型（ADT）？
实现栈和队列：这两种最基本的数据结构如何工作？
了解Java泛型和迭代的使用：如何编写类型安全且可复用的数据结构？

1.2 为什么第一章如此重要

算法分析是整个计算机科学的基石。如果你不能分析一个算法的效率，就无法在多个解决方案中做出正确的选择。本章介绍的Big-O表示法、数据抽象、栈和队列等概念，将贯穿后续所有章节。

Sedgewick在本章中特别强调了一个观点：算法不仅仅是能工作的代码，更是高效工作的代码。一个排序算法可能有多种实现方式，但它们之间的性能差异可能达到百万倍。学会分析这种差异，是成为优秀程序员的关键。

1.3 核心问题引导

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

为什么我们需要分析算法的效率？直接运行测试不就行了吗？

大O表示法为什么忽略常数因子？在什么情况下常数因子很重要？

栈和队列的底层实现有哪些选择？各自的优缺点是什么？

为什么要使用泛型？Java的类型擦除对泛型有什么影响？

数据抽象的意义是什么？为什么不能直接使用内置的数据结构？

如何衡量一个算法是"好"的？最坏情况和平均情况哪个更重要？

二、核心概念详解

2.1 算法分析基础

2.1.1 什么是算法

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

有限性：算法必须在有限步骤后终止
确定性：每个步骤都有明确的定义，无歧义
输入：有零个或多个输入
输出：有一个或多个输出
可行性：每个步骤都可以在有限时间内完成

2.1.2 为什么要分析算法

直接运行程序来测量时间（基准测试）有以下局限：

结果依赖于硬件环境
结果依赖于输入数据
无法预测更大规模输入的表现
无法进行理论比较

算法分析的目标是独立于硬件和具体实现，从数学上描述算法的效率。这使我们能够：

预测算法在大规模输入下的表现
比较不同算法的理论效率
识别性能瓶颈
做出明智的设计决策

2.1.3 大O表示法

大O表示法描述算法增长率的上界。它关注的是当输入规模n趋向无穷大时，算法的运行时间如何增长。

常见的时间复杂度等级（从快到慢）：

记号	名称	示例
O(1)	常数时间	数组访问、哈希表查找
O(log n)	对数时间	二分查找
O(n)	线性时间	线性搜索、遍历数组
O(n log n)	线性对数时间	归并排序、快速排序
O(n²)	平方时间	选择排序、插入排序
O(n³)	立方时间	矩阵乘法（朴素）
O(2ⁿ)	指数时间	穷举搜索
O(n!)	阶乘时间	旅行商问题（穷举）

大O表示法的核心规则：

// 规则1：忽略常数因子
// O(3n) = O(n)
// O(500) = O(1)

// 规则2：忽略低阶项
// O(n² + n) = O(n²)
// O(n³ + n² + n) = O(n³)

// 规则3：嵌套循环相乘
for (int i = 0; i < n; i++)        // O(n)
    for (int j = 0; j < n; j++)    // O(n)
        // O(1)
// 总计：O(n × n) = O(n²)

// 规则4：顺序执行取最大值
// O(n) + O(n²) = O(n²)

2.1.4 最好、最坏和平均情况

同一个算法对不同输入可能有不同的运行时间：

最好情况（Best Case）：最小运行时间，下界分析
最坏情况（Worst Case）：最大运行时间，上界分析，最重要
平均情况（Average Case）：期望运行时间，需要概率分析

java

// 线性搜索的三种情况
public static int linearSearch(int[] a, int key) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == key) return i;
    }
    return -1;
}

// 最好情况：key在第一个位置，O(1)
// 最坏情况：key在最后或不存在，O(n)
// 平均情况：key在任意位置等概率，O(n)

在实际应用中，我们通常关注最坏情况，因为它提供了性能保证。

2.2 数据抽象

2.2.1 抽象数据类型（ADT）

抽象数据类型定义了数据的逻辑结构和操作接口，而不涉及具体实现。常见的ADT包括：

栈（Stack）：后进先出（LIFO）
队列（Queue）：先进先出（FIFO）
集合（Set）：不重复元素的集合
符号表（Symbol Table）：键值对的集合

ADT的核心思想是封装：用户只需要知道"能做什么"，不需要知道"怎么做"。

2.2.2 Java泛型

泛型使数据结构可以适用于任意数据类型，同时保持类型安全：

java

// 不使用泛型 - 需要类型转换
Stack stack = new Stack();
stack.push("Hello");
String s = (String) stack.pop(); // 需要强制转换

// 使用泛型 - 类型安全
Stack<String> stack = new Stack<>();
stack.push("Hello");
String s = stack.pop(); // 不需要转换

Java泛型的实现使用类型擦除：编译器在编译时将泛型类型替换为Object（或上界），运行时不保留类型信息。这意味着：

不能创建泛型数组：new T[10] 不合法
不能使用基本类型：需要 Integer 而非 int
不能进行 instanceof 检查

2.3 栈（Stack）

栈是一种后进先出（LIFO）的数据结构，支持以下操作：

push(item)：将元素压入栈顶
pop()：弹出并返回栈顶元素
isEmpty()：判断栈是否为空
size()：返回栈中元素个数

2.3.1 链表实现

java

public class Stack<Item> implements Iterable<Item> {
    private Node first;
    private int size;
    
    private class Node {
        Item item;
        Node next;
    }
    
    public boolean isEmpty() {
        return first == null;
    }
    
    public int size() {
        return size;
    }
    
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        size++;
    }
    
    public Item pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        Item item = first.item;
        first = first.next;
        size--;
        return item;
    }
    
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        
        public boolean hasNext() {
            return current != null;
        }
        
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

链表实现的栈，所有操作都是O(1)时间。优点是动态大小，不需要预分配空间。缺点是每个元素需要额外的指针空间。

2.3.2 数组实现

java

public class ArrayStack<Item> implements Iterable<Item> {
    private Item[] items;
    private int size;
    
    public ArrayStack() {
        items = (Item[]) new Object[2];
        size = 0;
    }
    
    public void push(Item item) {
        if (size == items.length) resize(2 * items.length);
        items[size++] = item;
    }
    
    public Item pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        Item item = items[--size];
        items[size] = null; // 避免对象游离
        if (size > 0 && size == items.length / 4) 
            resize(items.length / 2);
        return item;
    }
    
    private void resize(int capacity) {
        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            copy[i] = items[i];
        }
        items = copy;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
}

数组实现使用动态扩容策略：当数组满时容量翻倍，当数组1/4满时容量减半。这种策略保证了摊还O(1)的时间复杂度。

2.4 队列（Queue）

队列是一种先进先出（FIFO）的数据结构，支持以下操作：

enqueue(item)：将元素加入队尾
dequeue()：移除并返回队首元素
isEmpty()：判断队列是否为空
size()：返回队列中元素个数

java

public class Queue<Item> implements Iterable<Item> {
    private Node first, last;
    private int size;
    
    private class Node {
        Item item;
        Node next;
    }
    
    public boolean isEmpty() {
        return first == null;
    }
    
    public int size() {
        return size;
    }
    
    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        if (isEmpty()) first = last;
        else oldlast.next = last;
        size++;
    }
    
    public Item dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        Item item = first.item;
        first = first.next;
        if (isEmpty()) last = null;
        size--;
        return item;
    }
    
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        
        public boolean hasNext() {
            return current != null;
        }
        
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

2.5 算法设计实例

2.5.1 二分查找

二分查找是在有序数组中查找元素的高效算法，时间复杂度为O(log n)：

java

public static int binarySearch(int[] a, int key) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (key < a[mid]) hi = mid - 1;
        else if (key > a[mid]) lo = mid + 1;
        else return mid;
    }
    return -1;
}

为什么是O(log n)？每次迭代都将搜索范围减半，从n到1需要除以log₂n次2。

2.5.2 归并排序简介

归并排序是分治思想的经典应用，时间复杂度为O(n log n)：

java

public static void mergeSort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, aux, lo, mid);
    mergeSort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++)
        aux[k] = a[k];
    
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else a[k] = aux[i++];
    }
}

三、实战案例

3.1 括号匹配

使用栈来检查括号是否正确匹配：

java

public class Parentheses {
    public static boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isBalanced("({[]})")); // true
        System.out.println(isBalanced("({[})]")); // false
        System.out.println(isBalanced("((()))")); // true
        System.out.println(isBalanced("(()"));    // false
    }
}

3.2 表达式求值

使用双栈算法（Dijkstra的双栈表达式求值）计算中缀表达式：

java

public class Evaluate {
    public static double evaluate(String expr) {
        Stack<String> ops = new Stack<>();
        Stack<Double> vals = new Stack<>();
        
        String[] tokens = expr.split("\\s+");
        for (String token : tokens) {
            if (token.equals("(")) {
                // 忽略左括号
            } else if (token.equals("+") || token.equals("*")) {
                ops.push(token);
            } else if (token.equals(")")) {
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("*")) v = vals.pop() * v;
                vals.push(v);
            } else {
                vals.push(Double.parseDouble(token));
            }
        }
        return vals.pop();
    }
    
    public static void main(String[] args) {
        System.out.println(evaluate("( 1 + ( 2 * 3 ) )")); // 7.0
    }
}

3.3 使用队列实现广度优先搜索

java

public class BFS {
    public static List<Integer> bfs(Graph G, int start) {
        boolean[] visited = new boolean[G.V()];
        Queue<Integer> queue = new Queue<>();
        List<Integer> order = new ArrayList<>();
        
        visited[start] = true;
        queue.enqueue(start);
        
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            order.add(v);
            
            for (int w : G.adj(v)) {
                if (!visited[w]) {
                    visited[w] = true;
                    queue.enqueue(w);
                }
            }
        }
        
        return order;
    }
}

四、本章小结

第1章建立了算法分析的基础框架：

算法分析：使用大O表示法描述算法的增长率，关注输入规模趋向无穷时的表现。忽略常数因子和低阶项，聚焦于增长率的本质。

数据抽象：通过ADT将数据的逻辑结构和操作接口与具体实现分离。泛型使数据结构可以适用于任意类型。

栈：后进先出（LIFO），可以用链表或数组实现。应用于括号匹配、表达式求值、函数调用等场景。

队列：先进先出（FIFO），可以用链表或数组实现。应用于BFS、任务调度、缓冲区等场景。

分治思想：将大问题分解为小问题，递归求解后合并结果。归并排序是分治的经典应用。

本章最重要的启示是：分析算法的效率是一项基本技能。在编写代码时，不仅要考虑"能不能工作"，更要考虑"效率如何"。掌握Big-O分析方法和基本数据结构，是学习后续高级算法的前提。

五、思考与练习

思考题

为什么大O表示法忽略常数因子？在什么情况下常数因子不能忽略？

栈的链表实现和数组实现各有什么优缺点？在实际应用中如何选择？

Java泛型的类型擦除带来了哪些限制？如何绕过这些限制？

为什么归并排序的时间复杂度是O(n log n)？如何从递归方程推导出来？

最坏情况分析和平均情况分析各有什么适用场景？为什么我们通常更关注最坏情况？

编程练习

使用两个栈实现一个队列，使得enqueue和dequeue操作的摊还时间复杂度为O(1)。

实现一个支持 findMax() 操作的栈，使得 push()、pop() 和 findMax() 都是O(1)时间。

编写一个程序，使用栈计算后缀表达式（如 3 4 + 2 * = 14）。

实现一个泛型的 Bag 数据结构（只支持添加和遍历，不支持删除），并使用它统计文件中不同单词的频率。