【算法基础】彻底吃透时间复杂度｜从原理、公式、例题、面试坑点全覆盖（超详细）

一、什么是时间复杂度1.1 核心定义时间复杂度不是统计代码运行的秒数因为- 不同电脑CPU性能不同- 不同编程语言执行速度不同- 同一代码不同环境耗时不同所以业界统一标准时间复杂度描述代码执行次数随数据规模 n 增长的趋势只看增长趋势不看常数、不看细节、不看具体耗时。1.2 为什么必须学1. 算法题能不能过时间限制全靠复杂度判断2. 面试必考手写分析、口头问原理3. 刷题提速核心先看复杂度再写代码二、大O表示法核心规则2.1 三大取舍规则必背1. 舍去常数项$$O(2n100) O(n)$$常数无论多大数据量大时完全无影响。2. 舍去低阶项$$O(n^2 n 50) O(n^2)$$高阶增长速度碾压低阶。3. 保留最高阶项最终只留增长最快的那一项。2.2 复杂度速度排序从快到慢O(1) O(logn) O(n) O(nlogn) O(n²) O(2ⁿ) O(n!)面试、刷题必考排序。三、七大常见复杂度逐一带代码精讲3.1 O(1) 常数复杂度特点无论n多大执行次数固定不变常见场景取值、赋值、四则运算、单次判断def func(n):a 1b 2c a bprint(c)无论 n1000 还是 n1000000执行次数完全不变。---3.2 O(n) 线性复杂度特点循环执行n次次数与n成正比for i in range(n):print(i)执行次数n次 → 趋势O(n)双层独立循环依然是 O(n)for i in range(n):passfor j in range(n):pass总次数 2n → 去常数 → O(n)---3.3 O(logn) 对数复杂度面试高频特征每次循环数据规模折半 / 成倍变化最经典二分、翻倍递增/递减i 1while i n:i * 2推导$$2^k n \Rightarrow k log_2n$$执行次数为 logn 次 → O(logn)口诀加减遍历是O(n)乘除翻倍是O(logn)---3.4 O(nlogn) 线性对数复杂度最常见优质算法复杂度典型算法快速排序、归并排序、sort()内置排序结构外层n次循环内层logn循环for i in range(n):j 1while j n:j * 2总复杂度$$n \times logn$$ → O(nlogn)---3.5 O(n²) 平方复杂度双层嵌套循环标配for i in range(n):for j in range(n):pass总次数 $$n^2$$ → O(n²)三层嵌套就是 $$O(n^3)$$算法里基本属于超时写法。---3.6 O(2ⁿ) 指数复杂度暴力递归专属数据稍大直接爆炸经典斐波那契递归def fib(n):if n 2:return 1return fib(n-1) fib(n-2)每一层分裂两次增长极快几乎无法处理n30的数据---3.7 O(n!) 阶乘复杂度全排列暴力枚举实际项目绝对不用只做理论了解。四、面试最容易踩的 6 个坑重点坑1把 logn 当成 n翻倍循环不是n次是logn次无数新手写错。坑2独立循环与嵌套循环分不清- 并列循环加法 $$nn \Rightarrow O(n)$$- 嵌套循环乘法 $$n\times n \Rightarrow O(n^2)$$坑3保留常数、保留低阶项面试写 $$O(2n)$$、$$O(n^2n)$$ 直接扣分坑4忽略递归复杂度递归不看代码行数看递归树节点数普通递归≠简单复杂度坑5双变量复杂度乱简化n、m 两个不同规模O(nm) 不能写成 O(n)只有其中一个是常数才可简化。坑6忘记空间复杂度递归栈、新数组、哈希表全部算空间开销五、刷题对应算法复杂度对照表- O(1)数组取值、变量运算- O(logn)二分查找、幂运算快速幂- O(n)单次遍历、双指针- O(nlogn)各种高级排序- O(n²)暴力两重循环、冒泡排序- O(2ⁿ)纯暴力递归搜索六、总结1. 时间复杂度只看最高阶增长趋势2. 常数、低阶项一律舍弃3. 单层遍历O(n)、翻倍遍历O(logn)、嵌套遍历幂次4. 算法能不能过题、优不优秀全看复杂度---下期预告空间复杂度详解 递归复杂度精准推导彻底搞定算法面试复杂度分析