知识点深化 · 复杂度
时间复杂度：用大 O 给算法算快慢
同样一个问题，暴力解法和聪明解法差几万倍。怎么衡量？就是时间复杂度——它不看具体几秒，只看当数据量 n 变大时，运行时间增长多快。这一页把常见复杂度排序、循环怎么数、排序算法复杂度一次理清，这是读懂所有算法的前提。
① 小白第一课怎么学（4 步走，约 50 分钟）
复杂度是衡量一个算法"跑得快不快、省不省内存"的尺子：
1看直观（10 分钟）
读第②③部分：把大 O 想象成"数据量翻 10 倍，耗时翻几倍"。
2记表（15 分钟）
背第④部分：常见复杂度排序、循环怎么数、主定理直觉。
3算例题（15 分钟）
精读第⑤部分，给几段代码数大 O。
4刷题纠错（10 分钟）
做第⑦⑩部分，错题回到第⑥部分。
本课小目标学完你要能：① 说出常见复杂度从快到慢的顺序；② 看一段代码大概估出时间复杂度；③ 区分最坏/平均/最好情况。
② 一图看懂：常见复杂度排队
读法：从左到右越来越慢。绿区（log n、n）很能打，黄区（n log n）是排序的好成绩，红区（n²、2ⁿ）数据一大就崩。
③ 先认识它：大 O 就是"看数据量涨 10 倍时耗时涨几倍"
想象你要在一个电话本里找"张三"：
· 翻一遍（O(n)）：100 条翻 100 次，1000 条翻 1000 次——条数涨 10 倍，耗时涨 10 倍。
· 二分（O(log n)）：每次折半，1000 条只要约 10 次，100 万条也只要约 20 次——涨得极慢。
· 两两比较所有组合（O(n²)）：100 条 1 万次，1000 条 100 万次——涨得飞快。
大 O 不关心具体几秒（那是硬件和常数），只关心随着数据量 n 变大，增长有多快。
大 O 只抓主要矛盾O(2n+100) 直接写成 O(n)，O(n²+n+1) 写成 O(n²)。常数、低阶项都扔掉——因为当 n 很大时，最高阶项起决定作用。
④ 完整体系与公式表
常见复杂度从快到慢
| 复杂度 | n=10 时 | 典型例子 | 评价 |
|---|
| O(1) | 1 | 取数组第 k 个元素、哈希表查找 | 最快 |
| O(log n) | ≈3 | 二分查找 | 极快 |
| O(n) | 10 | 遍历一遍数组 | 够用 |
| O(n log n) | ≈33 | 快排、归并排序 | 排序最佳 |
| O(n²) | 100 | 冒泡/选择排序、双重循环 | n 大就慢 |
| O(n³) | 1000 | 三重循环、矩阵相乘 | 很慢 |
| O(2ⁿ) | 1024 | 全子集枚举 | 几乎不可用 |
| O(n!) | 362 万 | 全排列 | 灾难 |
排序算法复杂度表
| 排序 | 最好 | 平均 | 最坏 | 空间 |
|---|
| 冒泡/选择 | O(n²) | O(n²) | O(n²) | O(1) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) |
递归主定理（直觉）T(n)=a·T(n/b)+f(n)
每层把子问题分成 a 个、规模缩到 1/b；比较 a 与 b^（f 的阶）。
直觉：递归树总节点数 vs 每层额外工作量，谁大谁主导。
时间 vs 空间时间复杂度=跑多久；空间复杂度=占多少内存。两者常要权衡，比如归并排序快但要 O(n) 额外空间。
⑤ 应用场景与典型例题
例1（单层循环）for i in range(n): print(i)，复杂度？
循环跑 n 次。
每轮固定操作，共 n 轮 → O(n)。
例2（嵌套循环）外层 i 跑 n 次，内层 j 也跑 n 次，复杂度？
嵌套相乘。
n×n = O(n²)。常见于冒泡排序、两两比较。
例3（折半）while n>1: n=n//2，复杂度？
每次砍一半。
n 除以 2，除到 1 要 log₂n 次 → O(log n)。二分查找就是这个。
估算口诀一层单层循环 O(n)；嵌套两层 O(n²)；每次折半 O(log n)；分治递归合并 O(n log n)。
⑥ 高频错误诊断（4 条）
错误 1：把常数写进大 OO(2n) 必须写成 O(n)，O(n/2) 也是 O(n)。大 O 忽略常数因子。
错误 2：低阶项舍不得扔O(n²+n) 就是 O(n²)，n 很大时 n² 碾压 n。
错误 3：混淆最好/平均/最坏快排平均 O(n log n)，但最坏（每次极不均衡）是 O(n²)。题目没说时一般谈最坏。
错误 4：以为 O(log n) 一定以 2 为底换底只是常数倍，O(log₂n)=O(log₁₀n)，大 O 里不写底数。
⑦ 考点与真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 排序 | 给算法说复杂度 | 记排序表 |
| 代码估算 | 看循环数大 O | 嵌套相乘、折半 log |
| 比较快慢 | 几个复杂度排序 | 背从快到慢 |
真题1. 下列哪个时间复杂度最快？
真题2. 二分查找的时间复杂度是？
真题3. 双重嵌套循环（各 n 次）的复杂度是？
真题4. 平均情况 O(n log n)、最坏 O(n²) 的排序是？
⑧ 必背公式卡
从快到慢：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) 必背顺序
单层循环：O(n) 跑 n 次
嵌套两层：O(n²) 相乘
折半：O(log n) 二分查找
快排/归并：平均 O(n log n) 排序最佳
大 O 规则：忽略常数、低阶 只留最高阶
底数：log 不写底数，换底是常数倍 O(log n)
⑨ 应用输出：用复杂度思维选型
建模场景：在 100 万条用户记录里查某个 ID
· 方案一：从第一条线性扫到尾 → O(n)=100 万次，每次查都慢。
· 方案二：先排序再二分 → 排序 O(n log n) 一次，之后每次 O(log n)≈20 次。
· 方案三：建哈希表 → O(n) 建一次，之后每次 O(1)，最快。
· 结论：查得频繁就用哈希/排序二分，别每次暴力扫。
口述训练说三句："大 O 只看最高阶；单层 O(n)、嵌套 O(n²)、折半 O(log n)；从快到慢 1、log n、n、n log n、n²。"
⑩ 分层练习 18 题（基础 6 + 中档 6 + 拔高 6）
▍基础 6 题
基础2O(n²+100n) 简化为？
O(n²)。
基础6O(n) 和 O(log n) 谁快？
O(log n) 快。
▍中档 6 题
中档7for i in range(n): for j in range(i,n) 复杂度？
总次数 n+(n−1)+…+1≈n²/2，仍是 O(n²)。
中档8归并排序最坏复杂度？
O(n log n)，稳定。
中档10O(n³) 和 O(2ⁿ) 谁更慢？
O(2ⁿ) 慢得多，指数爆炸。
中档11时间复杂度和空间复杂度区别？
时间=跑多久，空间=占多少内存。
中档12快排最坏复杂度？什么时候？
O(n²)，每次选的基准极不均衡（如已排序数组）。
▍拔高 6 题
拔高13T(n)=2T(n/2)+O(n) 的复杂度？
归并式，O(n log n)。
拔高14T(n)=T(n/2)+O(1) 的复杂度？
二分式，O(log n)。
拔高15堆排序空间复杂度？
原地排序，O(1)。
拔高16n=10⁶，O(n²) 算法大约要多少次？
10¹² 次，根本跑不完——这就是为什么不能暴力。
拔高17最好 O(n log n)、最坏 O(n²)、空间 O(1) 的排序？
堆排序（最坏也 n log n，空间 O(1)）。
拔高18为什么大 O 忽略常数和低阶？
n→∞ 时最高阶项主导增长，常数和低阶对增长趋势无影响。
⑪ 记忆口诀 + 7 天复习计划
三句口诀
① 大 O 只看最高阶，常数低阶全扔掉。
② 单层 n、嵌套 n²、折半 log n，排序最好 n log n。
③ 从快到慢记一遍：1、log n、n、n log n、n²、2ⁿ。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，背复杂度排序 | 按快慢排对 |
| 第 2 天 | 背排序表 + 基础 1-6 | 常见排序不混 |
| 第 3 天 | 做中档 7-12 | 会估循环复杂度 |
| 第 4 天 | 做拔高 13-18 | 认识主定理直觉 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述三句口诀 | 不看资料全说对 |
← 返回算法与AI总览