绪论：数据、模型与算法
数据与数学模型
数据是客观事物的符号表示，也是信息的载体。计算机围绕数据完成采集、传输、存储和处理；算法则从数据中得到所需结果。
数学模型是针对特定目的，对现实对象作取舍和抽象后得到的数学结构。建模时没有“越复杂越好”这一说，模型只需保留与当前问题有关的因素。例如人口增长可以先用指数模型
\[
x(t)=x_0e^{rt},
\]
但它没有考虑资源上限。加入承载量 \(x_m\) 后，可改用 Logistic 模型
\[
\frac{\mathrm dx}{\mathrm dt}=rx\left(1-\frac{x}{x_m}\right),
\qquad
x(t)=\frac{x_m}{1+\left(\frac{x_m}{x_0}-1\right)e^{-rt}}.
\]
同一问题往往有一串由简到繁的模型。先明确假设、输入、输出和适用范围，再谈计算方法。
算法及其评价
算法是解决特定问题的有限指令序列，具有五个基本特性：
- 有穷性：有限步后结束，每一步也能在有限时间内完成；
- 确定性：每条指令含义明确，不依赖含糊解释；
- 可行性：每一步都能由已有的基本操作在有限次执行后完成；
- 输入：有零个或多个输入；
- 输出：至少有一个输出。
评价算法不能只看“样例能跑”。通常还要看：
- 正确性：对所有合法输入都给出正确结果；
- 可读性：结构清楚，便于检查、维护和复用；
- 健壮性：能妥善处理非法输入和边界情况；
- 效率：合理使用时间和空间。
直接计时属于事后统计，结果会混入语言、编译器、硬件和运行负载的影响。复杂度分析则选取会反复执行的基本操作，在实现前估计其次数随问题规模 \(n\) 的增长规律。
渐进复杂度
若存在正常数 \(C,n_0\)，使得 \(n\ge n_0\) 时
\[
0\le T(n)\le C f(n),
\]
就记作 \(T(n)=O(f(n))\)。Big-O 描述渐进上界，常数因子和低阶项在这里被忽略。常见增长量级为
\[
O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!).
\]
分析循环时，顺序语句的代价相加，嵌套循环的迭代次数相乘；循环变量按倍数增长通常对应对数复杂度。例如
只执行 \(\lceil\log_2 n\rceil\) 次，因此为 \(O(\log n)\)。
几种课件中的典型计数可以放在一起看：
| 程序结构 | 基本操作次数 | 复杂度 |
|---|---|---|
| 三层各循环 \(n\) 次 | \(n^3\) | \(O(n^3)\) |
| 内层从当前 \(i\) 走到 \(n\) | \(n+(n-1)+\cdots+1\) | \(O(n^2)\) |
| 外层 \(i=1\ldots n\)，内层变量倍增 | \(\sum_i O(\log i)=O(\log n!)\) | \(O(n\log n)\) |
| 外层变量倍增，内层固定执行 10 次 | \(10\lceil\log_2n\rceil\) | \(O(\log n)\) |
同一算法还要区分最好、最坏和平均情况。以顺序查找为例，成功位置等可能时平均比较次数为
\[
\frac{1}{n}\sum_{i=1}^{n}i=\frac{n+1}{2}.
\]
空间复杂度包括指令、数据以及函数调用所需的环境空间。通常只统计除输入本身以外的额外空间；若额外空间为常数，称为原地算法。