本文适合：数据结构入门、考研复习、春招秋招算法面试、CSDN 学习笔记
一、前言
在学习数据结构与算法时，复杂度分析是最基础、最重要、也是面试必问的知识点。
它不依赖运行环境、不依赖测试数据，能提前预估算法的执行效率和内存占用，是判断代码好坏的核心依据。
本文从概念、计算规则、常见复杂度、代码案例、空间复杂度、面试真题全方位讲解，小白也能轻松看懂。
二、什么是时间复杂度？
时间复杂度：描述算法执行时间随数据规模 n 增长的变化趋势。
使用 大O表示法： T(n) = O(f(n))
计算四个原则:
1.只保留最高阶项
2.去掉最高阶项的系数
3.去掉常数项
4.只剩常数时记作O(1)
示例：
O(2n + 100) → O(n)
O(3n² + 5n + 9) → O(n²)
三、常见时间复杂度（极致紧凑表格）
表格
效率从高到低：
O(1) ＞ O(logn) ＞ O(n) ＞ O(nlogn) ＞ O(n²) ＞ O(n³) ＞ O(2ⁿ) ＞ O(n!)
四、代码示例 + 复杂度分析
- 常数阶 O(1)
执行次数固定，与 n 无关。
2. 线性阶 O(n)
单层循环，执行 n 次。
3. 平方阶 O(n²)
两层嵌套循环。
4. 对数阶 O(logn)
每次规模减半。
五、空间复杂度
空间复杂度：衡量算法临时占用内存的增长趋势。
O(1)：仅使用固定变量（原地算法）
O(n)：开辟长度为 n 的数组
O(n²)：开辟 n×n 二维数组
示例：
六、时间与空间的取舍
空间换时间：占用更多内存，提高运行速度（常用）
时间换空间：内存紧张时，牺牲速度节省空间
七、面试高频真题（必背）
二分查找时间复杂度？
答：O(logn)冒泡/选择排序复杂度？
答：O(n²)快速排序、归并排序复杂度？
答：O(nlogn)递归求斐波那契复杂度？
答：O(2ⁿ)大O表示法的意义？
答：表示算法效率的增长趋势，不依赖环境。
八、总结
时间复杂度看执行次数，空间复杂度看临时内存
复杂度越低，算法效率越高
日常开发优先优化时间复杂度
入门必须掌握：O(1)、O(logn)、O(n)、O(nlogn)、O(n²)
本文为数据结构基础系列，后续会更新链表、栈、队列、树、排序算法。
欢迎 👍点赞、⭐收藏、💬评论，一起进步！
