算法分析与复杂度

概念讲解

主定理

对于 T(n)=aT(n/b)+O(nd)T(n) = aT(n/b) + O(n^d)：

  1. 如果 a<bda < b^d，T(n)=O(nd)T(n) = O(n^d)
  2. 如果 a=bda = b^d，T(n)=O(ndlog⁡n)T(n) = O(n^d \log n)
  3. 如果 a>bda > b^d，T(n)=O(nlog⁡ba)T(n) = O(n^{\log_b a})

均摊分析

分析一系列操作的平均时间复杂度。

常见复杂度

算法 时间复杂度 空间复杂度
冒泡排序 O(n²) O(1)
选择排序 O(n²) O(1)
插入排序 O(n²) O(1)
快速排序 O(n log n) O(log n)
归并排序 O(n log n) O(n)
堆排序 O(n log n) O(1)
二分查找 O(log n) O(1)
DFS/BFS O(V + E) O(V)
Dijkstra O((V+E)logV) O(V)
Floyd O(V³) O(V²)

考点分析

初赛考查方式

  1. 选择题： 复杂度分析
  2. 程序阅读： 计算执行次数
  3. 填空题： 复杂度计算

常见题型

  • 主定理应用
  • 均摊分析
  • 复杂度比较

例题精讲

例题 1：主定理

题目： 求 T(n) = 2T(n/2) + O(n) 的复杂度。

解答：

a = 2, b = 2, d = 1
a = b^d (2 = 2^1)
T(n) = O(n^d log n) = O(n log n)

例题 2：均摊分析

题目： 分析 n 次 push_back 操作的均摊复杂度。

解答：

push_back 通常是 O(1)
偶尔需要扩容，是 O(n)
均摊复杂度：O(1)

练习题

  1. 用主定理求 T(n) = 4T(n/2) + O(n²) 的复杂度。
查看答案

O(n2log⁡n)O(n^2 \log n)

a = 4, b = 2, d = 2
a = b^d (4 = 2^2)
T(n) = O(n^d log n) = O(n^2 log n)
  1. 分析归并排序的时间复杂度。
查看答案

归并排序的时间复杂度：

  • 分解：O(log⁡n)O(\log n) 层
  • 每层合并：O(n)O(n)
  • 总计：O(nlog⁡n)O(n \log n)
  1. 比较各种排序算法的复杂度。
查看答案
算法 平均时间 最坏时间 空间 稳定性
冒泡排序 O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) 稳定
选择排序 O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) 不稳定
插入排序 O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) 稳定
快速排序 O(nlog⁡n)O(n \log n) O(n2)O(n^2) O(log⁡n)O(\log n) 不稳定
归并排序 O(nlog⁡n)O(n \log n) O(nlog⁡n)O(n \log n) O(n)O(n) 稳定
堆排序 O(nlog⁡n)O(n \log n) O(nlog⁡n)O(n \log n) O(1)O(1) 不稳定

易错点

⚠️ 注意：

  1. 主定理有三种情况
  2. 均摊分析要考虑一系列操作
  3. 复杂度是最坏情况的上界
  4. 注意空间复杂度