时间复杂度和空间复杂度
前端开发：重时间，轻空间
时间复杂度
随着输入数据规模（n）增长，计算量的变化趋势，趋势越陡说明算法执行消耗的时间越长
shell
# 常见类型
常数型 O(1)：无论输入规模如何，算法执行时间都是固定的。
对数型 O(log n)：每次操作将问题规模缩小一半。比如二分查找有序数组。
线性型 O(n)：随着输入规模的增大，执行时间线性增长。比如 forEach 遍历数组、数组 filter/map 方法。
线性对数型 O(n log n)：随着输入规模的增大，执行时间增长得相对较快，但仍比O(n^2)的时间复杂度要好。比如归并排序、快速排序（平均情况）。
平方型 O(n^2)：随着输入规模的增大，执行时间以平方的速度增长，这是最差的时间复杂度。比如双重 for 循环（如冒泡排序、嵌套遍历 DOM 节点）。
立方型 O(n^3)：随着输入规模的增大，执行时间以立方的速度增长，这是最差的时间复杂度。
指数型 O(2^n)：随着输入规模的增大，执行时间以指数的速度增长，这是最差的时间复杂度。
# 时间复杂度的等级通常按照增长速度由快到慢分为
常数型 < 对数型 < 线性型 < 线性对数型 < 平方型 < 立方型 < 2 的指数型
Ο(1) < Ο(log n) < Ο(n) < Ο(nlog n) < Ο(n2) < Ο(n3) ... < Ο(2^n)
# 如何计算时间复杂度（只关注循环 / 递归的核心操作）
常数型 —— 单次执行的算法
对数型 —— 单层遍历结合二分的算法
线性型 —— 直接单层遍历的算法
线对型 —— 双层遍历，其中一层遍历一层遍历二分的算法
平方型 —— 直接双层遍历的算法空间复杂度
随着输入数据规模（n）增长，额外存储空间的变化趋势，趋势越陡说明算法执行占用的空间越大
shell
# 常见类型
与时间复杂度类似，只是关注的是多余的存储空间
# 空间复杂度的等级通常按照增长速度由快到慢分为
常数型 < 对数型 < 线性型 < 线性对数型 < 平方型 < 立方型 < 2 的指数型
Ο(1) < Ο(log n) < Ο(n) < Ο(nlog n) < Ο(n2) < Ο(n3) ... < Ο(2^n)
# 如何计算时间复杂度
忽略常数项和低阶项：只关注随输入规模 n 增长的 “主导项”
忽略系数：系数不影响增长趋势，例如 O (2n) 简化为 O (n)、O (3n²) 简化为 O (n²)。
区分 “固定空间” 和 “可变空间”：固定空间（如单个变量、常量）不计入复杂度，可变空间（随 n 变化的数组、对象）才是计算核心。时间空间参照表
shell
操作场景 时间复杂度 空间复杂度 核心备注
数组访问指定索引 O(1) O(1) 直接通过下标定位，与数组长度无关
数组 forEach/map/filter O(n) O(1) 遍历所有元素，map/filter 返回新数组时空间 O (n)
数组 push/pop（尾部操作） O(1) O(1) 不改变数组整体结构，直接操作尾部元素
数组 shift/unshift（头部操作） O(n) O(1) 需重新排列所有元素的索引
数组查找目标元素（遍历） O(n) O(1) 逐个对比，最坏情况遍历全部元素
有序数组二分查找 O(logn) O(1) 每次缩小一半查找范围，仅适用于有序数组
对象属性访问 / 赋值 O(1) O(1) 哈希表结构，直接映射键值对
对象 for...in 遍历 O(k) O(1) k 为对象属性个数，与输入规模 n 无关
Map/Set 增删查改 O(1) O(k) k 为存储元素个数，比对象更稳定的哈希实现
DOM 查询（getElementById） O(1) O(1) 浏览器内部优化的快速定位
DOM 查询（getElementsByClassName） O(n) O(1) n 为文档节点总数，需遍历匹配类名
DOM 树递归遍历 O(n) O(d) n 为节点数，d 为树的深度（递归栈空间）
冒泡排序 / 选择排序 O(n²) O(1) 双重循环，原地排序，无额外空间开销
快速排序（平均情况） O(nlogn) O(logn) 递归调用栈空间，最坏情况 O (n)
归并排序 O(nlogn) O(n) 需额外数组存储合并结果，稳定排序
数组去重（新数组存储） O(n) O(n) 用 Set 或对象记录已存在元素，空间换时间
斐波那契数列（递归） O(2ⁿ) O(n) 大量重复计算，递归栈深度为 n
斐波那契数列（迭代） O(n) O(1) 用变量记录中间结果，无额外空间开销