算法基础
算法（Algorithm）是解决特定问题的一系列明确、有限的步骤。
理解算法的基本概念和效率分析方法，是学习数据结构与算法的重要前提。
算法的定义与特性
在计算机科学中，算法是指令的有限序列，每条指令表示一个或多个操作。
一个合格的算法必须具备以下五个基本特性：
| 特性 | 含义 | 反例 |
|---|---|---|
| 输入 | 有零个或多个外部输入 | 无输入也是合法的，如生成随机数 |
| 输出 | 至少产生一个结果 | 没有任何输出的"算法"是无意义的 |
| 确定性 | 每一步骤的含义必须清晰无歧义 | "适当增加"这种模糊描述不可接受 |
| 有限性 | 必须在有限步骤内结束，不能无限循环 | 操作系统本身不是算法，它理论上永远运行 |
| 可行性 | 每一步都能通过基本操作实现 | "除以零"不可行，"一步完成排序"也不可行 |
算法的"有限性"与程序的"死循环"并不矛盾。一个程序可以因为 bug 而陷入死循环，但算法本身必须能在有限步骤内结束。区别在于：算法是"设计意图"层面的概念，程序是"实际执行"层面的概念。
算法的表示方法
在设计和交流算法时，常用两种表示方式。
伪代码（Pseudocode）
伪代码使用接近自然语言、但具有一定结构化格式的文字来描述算法逻辑。
它不依赖具体编程语言语法，便于快速表达思路。
例如，在一组数字中查找最大值的伪代码：
算法：FindMax 输入：数组 A，长度 n 输出：A 中的最大值 1. max = A[0] 2. for i = 1 to n-1: 3. if A[i] > max: 4. max = A[i] 5. return max
流程图（Flowchart）
流程图通过图形化的方式直观展示算法的执行流程。
上图展示了 FindMax 算法的完整执行流程：从输入数组开始，初始化当前最大值，然后依次比较每个元素，如果找到更大的值就更新最大值，遍历完成后输出结果。
流程图中的符号约定：
| 符号形状 | 含义 |
|---|---|
| 圆角矩形（或椭圆） | 开始 / 结束 |
| 矩形 | 处理步骤 |
| 菱形 | 判断 / 分支 |
| 平行四边形 | 输入 / 输出 |
| 箭头 | 流程方向 |
算法效率分析
设计好算法后，还需要评估它的效率。这主要通过两个维度来衡量。
时间复杂度
时间复杂度描述的是：随着输入规模 n 的增大，算法执行所需的基本操作次数的增长趋势。
注意，我们关心的是"增长趋势"，而不是"精确的执行次数"。因为对于大规模输入，常数倍数的差异远不如增长趋势的差异重要。
空间复杂度
空间复杂度描述的是：随着输入规模 n 的增大，算法执行过程中所需额外内存空间的增长趋势。
这里强调"额外"空间，指的是除了存储输入数据本身之外，算法还需要多少辅助空间。
时间和空间往往是一对矛盾——用空间换时间，或用时间换空间，是算法设计中常见的权衡策略。例如：哈希表用额外的存储空间换取了 O(1) 的查找时间；而原地排序算法则用稍多的计算步骤避免了额外空间的消耗。
大 O 表示法
大 O 表示法（Big O Notation）是衡量时间复杂度和空间复杂度最常用的数学工具。
它描述的是算法在最坏情况下，随着输入规模 n 增大，运行时间或空间占用的增长趋势上界。
定义：如果存在正常数 c 和 n0，使得当 n ≥ n0 时，总有 T(n) ≤ c × f(n)，则记作 T(n) = O(f(n))。
通俗理解：大 O 表示法忽略常数因子和低阶项，只关注增长最快的项。
例如：如果算法需要 3n² + 100n + 500 次操作，当 n 足够大时，n² 项主导增长，所以我们说它是 O(n²)。
常见复杂度等级
上图直观展示了各复杂度等级随输入规模 n 增长的变化趋势。
| 表示法 | 名称 | n=10 | n=1000 | 典型算法 |
|---|---|---|---|---|
| O(1) | 常数阶 | 1 | 1 | 数组按下标访问、哈希表查找 |
| O(log n) | 对数阶 | ~3 | ~10 | 二分查找、平衡 BST 操作 |
| O(n) | 线性阶 | 10 | 1000 | 线性查找、遍历数组 |
| O(n log n) | 线性对数阶 | ~30 | ~10000 | 归并排序、快速排序（平均） |
| O(n²) | 平方阶 | 100 | 1000000 | 冒泡排序、选择排序 |
| O(2ⁿ) | 指数阶 | 1024 | 天文数字 | 暴力求解子集问题 |
从表中可以看出，当 n=1000 时，O(1) 仍然只需要 1 次操作，O(n) 需要 1000 次，而 O(n²) 需要 100 万次。
在大规模数据场景下，选择合适复杂度的算法可能带来数量级的性能差异。
在实际编程中，应尽量保证核心算法的复杂度不超过 O(n log n)。当复杂度达到 O(n²) 或更高时，需要格外关注输入规模是否可控，以及是否存在更优的替代方案。
时间复杂度计算示例
以下是一段简单的 C 代码及其时间复杂度分析：
实例
/* 函数功能：计算数组元素之和
时间复杂度：O(n)
n 为数组长度，循环执行 n 次，每次循环执行常数次操作 */
int sumArray(int arr[], int n) {
int total = 0; /* O(1) — 赋值操作，执行 1 次 */
for (int i = 0; i < n; i++) { /* 循环体 */
total += arr[i]; /* O(1) — 加法和赋值，执行 n 次 */
}
return total; /* O(1) — 返回操作，执行 1 次 */
}
/* 整体时间复杂度：O(1 + n + 1) = O(n)
低阶常数项被忽略 */
int main() {
int nums[] = {5, 10, 15, 20, 25};
int size = sizeof(nums) / sizeof(nums[0]);
int result = sumArray(nums, size);
printf("数组元素之和: %d\n", result); /* 输出: 数组元素之和: 75 */
return 0;
}
再看一个嵌套循环的例子：
实例
/* 函数功能：打印 n×n 的乘法表
时间复杂度：O(n²)
外层循环 n 次，内层循环 n 次，共 n×n 次 */
void printMulTable(int n) {
for (int i = 1; i <= n; i++) { /* 外层循环 O(n) */
for (int j = 1; j <= n; j++) { /* 内层循环 O(n)，嵌套后总次数 n² */
printf("%d\t", i * j); /* O(1) 操作 */
}
printf("\n");
}
}
/* 整体时间复杂度：O(n × n) = O(n²) */
int main() {
printMulTable(5); /* 输出 5×5 乘法表 */
return 0;
}
空间复杂度计算示例
空间复杂度关注的是算法执行过程中额外分配的内存空间。
实例
#include <stdlib.h> /* malloc/free 所在的头文件 */
/* 函数功能：创建一个新数组，存储原数组的平方值
空间复杂度：O(n) — 分配了长度为 n 的新数组 */
int* squareArray(int arr[], int n) {
int* result = (int*)malloc(n * sizeof(int)); /* 额外分配 n 个 int 的空间 */
if (result == NULL) {
return NULL; /* malloc 失败时返回 NULL */
}
for (int i = 0; i < n; i++) {
result[i] = arr[i] * arr[i];
}
return result;
}
/* 空间复杂度 O(n)：
- 输入数组 arr 不计入（属于输入本身）
- result 数组额外分配 n 个 int，这是额外空间
- 变量 i 是常量空间 O(1)，被 O(n) 主导 */
int main() {
int nums[] = {1, 2, 3, 4, 5};
int n = 5;
int* squared = squareArray(nums, n);
if (squared != NULL) {
for (int i = 0; i < n; i++) {
printf("%d ", squared[i]); /* 输出: 1 4 9 16 25 */
}
printf("\n");
free(squared); /* 手动释放动态分配的内存 */
}
return 0;
}
初学者常见误区：时间复杂度和空间复杂度分析的是"增长趋势"而非精确值。常量系数、低阶项、以及不同编程语言的差异都会被大 O 表示法忽略。因此 O(2n) 和 O(n) 是等价的——它们都代表线性增长。