Chap1 绪论与算法分析

1、学习目标

本章先回答一个问题：为什么同样能得到结果的程序，仍然要比较“好坏”。数据结构后面每一章都会反复讨论时间、空间、最坏情况、平均情况和分摊意义，所以绪论不是开场白，而是整门课的计量工具。

PDF 课件	内容
`01.Introduction.A.Computation.pdf`	计算、算法、正确性
`01.Introduction.B.Computational_Models.pdf`	计算模型、RAM、基本操作
`01.Introduction.C.Big_o.pdf`	大 O 记号和增长阶
`01.Introduction.D.Algorithm_analysis.pdf`	复杂度估计和常见级数
`01.Introduction.E.Iteration_Recursion.pdf`	迭代与递归
`01.Introduction.F.Dynamic_Programming.pdf`	动态规划入口
`01.Introduction.X1.Limitation.pdf`	算法和计算的限制
`01.Introduction.X2.Sorting_Lower_Bound.pdf`	排序问题下界

算法是一组有限步骤，通常要求：

数据结构课程里，算法不是孤立存在的。一个操作的复杂度往往取决于底层结构：顺序表插入可能移动大量元素，链表插入可以改指针，但查找又没有随机访问。

常用 RAM 模型把以下操作近似视为常数时间：

1	-*/%、赋值、比较、数组下标访问、指针读写、函数基本跳转

这个模型不是硬件真实细节，而是为了比较算法增长趋势。真正写项目时还要考虑缓存、分支预测、内存分配等工程因素；但在数据结构课里，先把输入规模 n 和基本操作次数说清楚。

常见增长阶：

1	O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)

复盘时不要只背顺序，要能解释：

常见求和：

循环估计流程：

for (int i = 1; i <= n; i *= 2) {
    work();
}
// i 每次翻倍，执行次数约 log2(n)

for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
        work();
    }
}
// 次数为 n + (n-1) + ... + 1 = O(n^2)

递归分析要抓住两个东西：每层做多少事，问题规模如何缩小。

朴素 Fibonacci 的问题是重复求解子问题：

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

改成迭代或记忆化后，可以把复杂度降到 O(n)：

int fib(int n) {
    int a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        int c = a + b;
        a = b;
        b = c;
    }
    return a;
}

动态规划适用于两类特征明显的问题：

特征	含义
最优子结构	大问题的最优解能由小问题最优解组合出来
重叠子问题	递归过程中反复求解同一批子问题

基本步骤：

数据结构课里，动态规划不是主线，但它帮助理解“算法设计不是只换结构，还要换求解方式”。

下界讨论的是：不是某个算法不够聪明，而是问题本身至少要付出多少代价。

比较排序的经典结论：

1	任何基于比较的排序算法，最坏情况下需要 Ω(n log n) 次比较。

理由可以用决策树理解：

所以归并排序、堆排序的 O(n log n) 在比较排序模型下已经达到最优阶。