复杂度分析
复杂度分析是算法分析的核心，用于评估算法在输入规模增大时的效率变化趋势。
多重循环类问题
对于嵌套循环的复杂度分析，关键在于确定循环变量的更新方式与退出条件的关系。
基本方法：找到循环退出条件的依赖变量 x，每次循环更新的变量 y，通过 x 与 y 的关系找到每次循环 y 的变化值 dy，对比循环退出条件即可得到循环次数。若内层循环次数依赖于外层循环，则先计算外层循环次数，再对每层内层循环次数求和。
常见复杂度类型
- 常数时间 O(1)：与输入规模无关
- 对数时间 O(log n)：二分法
- 线性时间 O(n)：单层遍历
- 线性对数时间 O(n log n)：分治算法
- 平方时间 O(n²)：双层嵌套循环
- 指数时间 O(2ⁿ)：暴力枚举
链接到
- 上一个知识点：无（本章第一个知识点）
- 下一个知识点：1.2 递归函数