算法复杂度

概述

算法复杂度用于描述算法执行所需资源量随输入规模增长的变化趋势，主要包括时间复杂度和空间复杂度。

关键内容

1. 时间复杂度：
2. 描述算法执行时间随输入规模增长的趋势
3. 常见复杂度等级：O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)

4. 影响程序性能的关键因素

5. 空间复杂度：

6. 描述算法所需存储空间随输入规模增长的趋势

7. 包括输入空间、辅助空间和输出空间

8. 大O表示法：

9. 渐进上界表示法，关注最高次项
10. 忽略常数因子和低阶项

11. 便于比较不同算法的效率

12. 复杂度分析技巧：

13. 循环分析：嵌套循环通常产生相乘的复杂度
14. 递归分析：使用主定理或递归树
15. 最坏/平均/最好情况分析

来源

• 代码优化 — 算法效率评估基础

相关

• 代码优化 — relates_to
• 数据结构 — relates_to
• 排序算法 — relates_to