本文适合数据结构入门、考研复习、春招秋招算法面试、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²)本文为数据结构基础系列后续会更新链表、栈、队列、树、排序算法。欢迎 点赞、⭐收藏、评论一起进步
