算法基本概念与分析
🎯 一句话秒杀：算法分析就是回答"这个程序跑多快"（时间复杂度）和"占多少空间"（空间复杂度）——用大O表示法。
一、算法的定义
算法的五个特性（回顾）
| 特性 | 含义 | 例子 |
|---|---|---|
| 有穷性 | 有限步内结束 | 死循环违反此特性 |
| 确定性 | 每一步含义明确 | "取较大的数"→歧义 |
| 可行性 | 能通过有限次基本运算实现 | |
| 输入 | 0个或多个外部输入 | |
| 输出 | 至少1个输出结果 |
算法 vs 程序（重要！）
| 算法 | 程序 | |
|---|---|---|
| 有穷性 | ✅ 必须满足 | ❌ 可以不满足（如操作系统在无限循环） |
| 描述方式 | 自然语言/流程图/伪代码 | 编程语言 |
| 执行者 | 人/计算机 | 计算机 |
二、时间复杂度分析
推导方法（重点！）
口诀： 找循环 → 算次数 → 取最高阶 → 去常数
c
// 例1：单层循环 O(n)
for (int i = 0; i < n; i++) {
sum += arr[i];
}
// 执行n次 → O(n)
// 例2：双层嵌套 O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
arr[i][j] = 0;
// 执行n×n次 → O(n²)
// 例3：每次减半 O(log n)
while (n > 0) {
printf("%d", n);
n /= 2; // n每次除以2
}
// 执行log₂n次 → O(log n)
// 例4：多次循环取最高阶
for (i = 0; i < n; i++) // O(n)
sum += arr[i];
for (i = 0; i < n; i++) // O(n²)
for (j = 0; j < n; j++)
arr[i][j] = 0;
// 总复杂度 = O(n) + O(n²) = O(n²) ← 取最高阶
// 例5：递归斐波那契 O(2ⁿ)
int fib(int n) {
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
// 调用树是指数级增长 → O(2ⁿ)常见复杂度排序
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
常数 对数 线性 线性对数 平方 指数 阶乘
最好 ←—————————————————————————————————————————→ 最差
🚨 红牌警告
时间复杂度只看"最坏情况"和"平均情况" 快排最坏 O(n²)，但平均 O(n log n)—有实际价值 而插入排序最坏 O(n²)，平均也是 O(n²)—实际价值不如快排
三、空间复杂度分析
算法运行过程中需要的额外存储空间
c
// O(1)—只用了固定几个变量
int sum(int arr[], int n) {
int s = 0; // s是额外变量
for (int i = 0; i < n; i++)
s += arr[i];
return s;
}
// O(n)—用了一个额外数组（副本）
int *copy = (int *)malloc(n * sizeof(int));
// O(n)—递归深度占栈空间
int fact(int n) {
if (n <= 1) return 1;
return n * fact(n-1); // 递归深度n，占n层栈空间
}
// 空间复杂度 O(n)四、算法设计的方法
常用算法策略
| 策略 | 思想 | 例子 |
|---|---|---|
| 分治法 | 分而治之 | 快排、归并、二分查找 |
| 动态规划 | 子问题最优→全局最优 | 背包问题、最短路径 |
| 贪心法 | 每一步局部最优 | Prim、Kruskal、Dijkstra |
| 回溯法 | 尝试+撤销 | 八皇后、迷宫 |
| 递归 | 自己调用自己 | 阶乘、斐波那契 |
五、大O表示法的数学定义
存在正数 c 和 n₀，使得对所有 n ≥ n₀，有 T(n) ≤ c·f(n) 则称 T(n) = O(f(n))
简单理解： 当 n 足够大时，T(n) 的增长速度不超过 f(n) 的常数倍
时间复杂度计算练习
c
// 练习1：分析以下代码的时间复杂度
int i = 1;
while (i <= n) {
i = i * 2;
}
// 答案：O(log₂n)
// 练习2：
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
sum++;
// 答案：n + (n-1) + ... + 1 = n(n+1)/2 → O(n²)
// 练习3：
for (int i = 0; i < n; i++)
func(); // func()的时间复杂度是O(log n)
// 答案：O(n log n)📝 闭卷真题挑战
（点击下方空白查看答案）
1. 算法必须满足的五个特性？
2. 算法和程序的最主要区别？
3. 以下代码的时间复杂度？
for(i=0; i<n; i++)
for(j=0; j<m; j++)
arr[i][j]=0;
4. O(1), O(n), O(n²), O(log n), O(2ⁿ) 按效率从高到低排序
5. 递归求斐波那契数列第n项的时间复杂度是？👆 点击展开答案
- 有穷性、确定性、可行性、输入、输出
- 算法必须满足有穷性，程序可以不满足（如操作系统永远在运行）
- O(n×m)（两层循环，外层n次，内层m次）
- O(1) > O(log n) > O(n) > O(n²) > O(2ⁿ)（从快到慢）
- 实际上 O(1) 最快，O(2ⁿ) 最慢
- O(2ⁿ)（指数级——每个fib(n)会分裂出两个递归调用）
📖 教材习题对照
| 教材习题 | 知识点 | 难度 |
|---|---|---|
| 习题1.3 | 算法特性 | ⭐ |
| 习题1.4 | 时间复杂度分析 | ⭐⭐ |
| 习题1.5 | 空间复杂度分析 | ⭐⭐ |
| 习题1.6~1.8 | 综合算法分析 | ⭐⭐⭐ |
对应教材：严蔚敏《数据结构》C语言版 第2版 → 第1章 绪论 对应考试大纲：考点20 — 算法基本概念 + 考点21 — 算法分析初步
📺 配套视频
复习到本考点 → 先看视频补讲，再刷上面「闭卷挑战」。