CS61B 课程笔记（Lecture 18 Asymptotics II）

8.3 渐进分析 II · Hug61B

1. 运行时间分析

定义：运行时间分析是对程序执行时间的定量评估，目的是了解在不同输入规模下，程序的运行时间如何变化。
核心问题：本质上是在询问“执行这些操作需要多长时间？”这一过程无法简单机械化，特别是对于复杂算法。

2. 成本模型

概念：成本模型是分析运行时间时选择的一种方法。选择某个特定操作（如数组访问、比较等）并计算其在输入规模变化下的数量。
目标：找出在输入规模 N 增长时，计数最多的操作，这通常决定了算法的总体复杂度。

3. 重要的求和公式

线性求和： \(1 + 2 + 3 + \ldots + N \in Θ(N^2)\)
- 推导：该求和可以通过公式 \(\frac{N(N+1)}{2}\) 计算得出，简化后为 \(Θ(N^2)\)。
指数求和： \(1 + 2 + 4 + 8 + \ldots + N \in Θ(N)\)
- 推导：这是一个等比数列的求和，最后一项 \(N\) 的数量级是线性的，因此可以归纳为 \(Θ(N)\)。

4. 练习的重要性

学习方法：深入理解运行时间分析需要大量的练习和经验积累。通过项目和课后习题来巩固所学知识。
建议：尽管在项目 2 中可能时间紧迫，但建议在有空余时间时，回顾讲座中的内容并完成相关习题。

5. 深入理解

复杂度的意义：了解复杂度的本质可以帮助你在实际应用中选择合适的算法。高复杂度算法在大规模数据集上可能表现不佳，因此应优先考虑低复杂度算法。

6. 实际示例

示例1：嵌套循环的时间复杂度分析

public void nestedLoopExample(int N) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // 进行一些常数时间的操作
            System.out.println(i + j);
        }
    }
}

分析：外层循环运行 N 次，内层循环也运行 N 次，总操作次数为 \(N \times N = N^2\)，因此时间复杂度为 \(Θ(N^2)\)。

示例2：选择数据结构的性能对比

import java.util.ArrayList;
import java.util.LinkedList;

public class DataStructureExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        LinkedList<Integer> linkedList = new LinkedList<>();

        // 向 ArrayList 和 LinkedList 添加元素
        for (int i = 0; i < 10000; i++) {
            arrayList.add(0, i); // 在头部插入
            linkedList.add(0, i); // 在头部插入
        }
    }
}