01-复杂度分析¶
重要性：⭐⭐⭐⭐⭐ 实用度：⭐⭐⭐⭐⭐ 学习时间：2-3天 必须掌握：是
为什么学复杂度分析？¶
复杂度分析能帮你做什么？¶
- 评估代码的效率好坏：知道哪段代码更快
- 预测程序在不同数据规模下的表现：10条数据vs100万条数据
- 选择最优的算法和数据结构：知道什么时候用数组，什么时候用哈希表
- 通过技术面试（必考！）：面试官必问的问题
📖 核心概念¶
什么是复杂度？¶
复杂度是衡量算法效率的指标，回答两个核心问题： - 时间复杂度：数据量变大时，程序运行时间增长多少？ - 空间复杂度：数据量变大时，程序内存占用增长多少？
大O表示法（Big O Notation）¶
大O表示法描述算法运行时间或空间需求随输入规模增长的上界（渐进上界）。
数学定义¶
\[T(n) = O(f(n))\]
表示存在正常数 \(c\) 和 \(n_0\)，使得对所有 \(n \geq n_0\)，有 \(0 \leq T(n) \leq c \cdot f(n)\)。
为什么只看"最高阶项"？¶
Python
# 假设某算法需要执行：3n² + 100n + 50 步
当 n = 10: 3×100 + 1000 + 50 = 1350 步
当 n = 1000: 3×1000000 + 100000 + 50 = 3100050 步
当 n = 10000: 3×100000000 + 1000000 + 50 = 301000050 步
关键洞察：当n变大时，n²这项的增长速度远远超过其他项！ - n从1000变到10000（10倍），n²变大了100倍！ - 所以我们只关心增长最快的那一项，写成 O(n²)
常见复杂度排序（从快到慢）：
Text Only
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
│ │ │ │ │ │ │ │
│ │ │ │ │ │ │ └─ 阶乘（灾难级慢）
│ │ │ │ │ │ └─ 指数（极慢，尽量避免）
│ │ │ │ │ └─ 立方（很慢）
│ │ │ │ └─ 平方（注意！数据大时会很慢）
│ │ │ └─ 线性对数（排序算法的目标）
│ │ └─ 线性（遍历一次，可以接受）
│ └─ 对数（非常快！每步减半）
└─ 常数（最快！与数据量无关）
图：不同时间复杂度的增长趋势对比
🎯 时间复杂度详解¶
1. O(1) - 常数时间¶
特点：执行时间与数据规模无关
示例：数组访问、哈希表查找
Python
# Python示例
def get_first(arr):
return arr[0] # 无论数组多大，都是一步操作
def hash_lookup(d, key):
return d[key] # 哈希表查找，平均O(1)
C++
// C++示例
int getFirst(vector<int>& arr) {
return arr[0]; // O(1)
}
int hashLookup(unordered_map<int, int>& mp, int key) {
return mp[key]; // 平均O(1)
}
2. O(log n) - 对数时间¶
特点：每一步将问题规模减半，非常高效
Text Only
数据量 | O(n) 需要多少步 | O(log n) 需要多少步
----------- | ---------------- | -------------------
10 | 10 | 3
100 | 100 | 7
1,000 | 1,000 | 10
100万 | 1,000,000 | 20
10亿 | 1,000,000,000 | 30
惊人对比：10亿个数据，O(n)要10亿次操作，O(log n)只要30次！
经典例子：二分搜索¶
场景：在有序数组中查找一个数
Python
# 二分搜索
def binary_search(arr, target):
"""
在有序数组中查找target
每次排除一半的元素
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # 取中间位置
if arr[mid] == target:
return mid # 找到了！
elif arr[mid] < target:
left = mid + 1 # 目标在右半边，丢弃左半边
else:
right = mid - 1 # 目标在左半边，丢弃右半边
return -1 # 没找到
执行过程示例（在[1,3,5,7,9,11,13,15]中找7）：
图：二分搜索算法的可视化演示
3. O(n) - 线性时间¶
特点：遍历所有元素一次
示例：遍历数组、链表
Python
# 查找最大值
def find_max(arr):
max_val = arr[0]
for val in arr: # 遍历一次
if val > max_val:
max_val = val
return max_val
4. O(n log n) - 线性对数时间¶
特点：高效的排序算法复杂度
示例：快速排序、归并排序、堆排序
Python
# 快速排序
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
5. O(n²) - 平方时间¶
特点：嵌套循环，数据规模大时要避免
示例：冒泡排序、简单嵌套循环
Python
# 冒泡排序（低效！）
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 外层循环 O(n)
for j in range(n - 1): # 内层循环 O(n)
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 总复杂度：O(n²)
何时避免：数据量 > 10000时，O(n²)会非常慢
图：嵌套循环的执行模式，展示O(n²)复杂度的来源
6. O(2ⁿ) - 指数时间¶
特点：极其低效，只适用于小规模数据
示例：递归计算的斐波那契数列（无优化）
优化方法：用动态规划降到O(n)
💾 空间复杂度详解¶
常见空间复杂度¶
O(1) - 常数空间¶
O(n) - 线性空间¶
Python
def reverse_array(arr):
result = [] # 创建了与输入大小相同的空间
for val in arr:
result.insert(0, val)
return result
O(n²) - 二维空间¶
🧮 复杂度计算技巧¶
技巧1：只关注最高阶项¶
Python
# 复杂度 = O(n² + n + 1) = O(n²)
# 因为 n² 增长最快，其他项可以忽略
for i in range(n): # O(n)
for j in range(n): # O(n²)
print(i, j)
for k in range(n): # O(n)
print(k)
print("done") # O(1)
技巧2：加法法则 vs 乘法法则¶
Python
# 加法法则：顺序执行的代码，复杂度相加
for i in range(n): # O(n)
print(i)
for j in range(n): # O(n)
print(j)
# 总复杂度：O(n) + O(n) = O(2n) = O(n)
# 乘法法则：嵌套循环，复杂度相乘
for i in range(n): # O(n)
for j in range(n): # O(n)
print(i, j)
# 总复杂度：O(n) × O(n) = O(n²)
技巧3：递归复杂度分析¶
Python
# 递归公式：T(n) = T(n/2) + O(1) → O(log n)
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
📊 复杂度对比表¶
| 复杂度 | n=10 | n=100 | n=1,000 | n=10,000 | 适用场景 |
|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 数组访问、哈希查找 |
| O(log n) | 3 | 7 | 10 | 13 | 二分搜索 |
| O(n) | 10 | 100 | 1,000 | 10,000 | 遍历数组 |
| O(n log n) | 30 | 700 | 10,000 | 130,000 | 快速排序、归并排序 |
| O(n²) | 100 | 10,000 | 1,000,000 | 100,000,000 | 简单嵌套循环 |
| O(2ⁿ) | 1,024 | 1.27×10³⁰ | ∞ | ∞ | 指数级递归 |
结论：在大数据场景下，O(log n)和O(n)是理想的复杂度
图：不同复杂度在不同数据规模下的操作次数对比
🎯 实战练习¶
练习1：分析代码复杂度¶
Python
# 问题1：这段代码的复杂度？
def foo(arr):
total = 0
for i in range(len(arr)):
for j in range(i, len(arr)):
total += arr[i] * arr[j]
return total
# 答案：O(n²)
# 解释：外层循环n次，内层循环平均n/2次
练习2：优化代码¶
Python
# 问题：如何优化这段O(n²)的代码？
def find_duplicates(arr1, arr2):
duplicates = []
for val1 in arr1:
for val2 in arr2: # O(n²)
if val1 == val2:
duplicates.append(val1)
return duplicates
# 优化方案：使用哈希表
def find_duplicates_optimized(arr1, arr2):
set2 = set(arr2) # O(n)
duplicates = []
for val1 in arr1: # O(n)
if val1 in set2: # O(1)
duplicates.append(val1)
return duplicates
# 优化后复杂度：O(n)
📝 学习检查清单¶
完成以下任务，表示你已经掌握了复杂度分析：
- 能背诵常见复杂度的排序
- 能快速计算简单代码的时间复杂度
- 能识别O(n²)的嵌套循环
- 能用大O表示法描述自己代码的复杂度
- 理解为什么哈希表查找比线性查找快
- 完成至少5道复杂度分析练习题
🔗 下一步¶
掌握复杂度分析后，继续学习： - 02-数组详解 - 学习数组和链表
📚 推荐阅读¶
- 《算法（第4版）》第1章：算法分析
- 大O表示法可视化