时间和空间复杂度
🎯 引言
掌握时间复杂度和空间复杂度的基本概念及计算方法，可以帮助你更有效地分析和优化前端代码性能，提升程序的执行效率和资源利用率。通过丰富的代码示例，理解不同算法和代码结构对复杂度的影响，为写出高效前端程序打下坚实基础。
⏰ 什么是时间复杂度？
时间复杂度简单来说就是一个算法执行所需要的时间，随着输入数据规模的增长，这个时间会发生怎样的变化。
举个生活中的例子：
你去超市买水果，如果你只买一颗苹果，花费的时间很短；如果你要买一篮子水果，那花的时间就会增加。时间复杂度就是帮我们估算买水果时间随着数量增长的增长速度。
时间复杂度常用的大O表示法有：O(1)、O(n)、O(n²)、O(log n) 等，下面用代码帮你理解。
🐢 示例 1：O(1) — 常数时间复杂度
function printFirstElement(arr) {
console.log(arr[0]);
}
无论数组多大，这段代码只访问一次元素，耗时固定，时间复杂度是 O(1)。
🐇 示例 2：O(n) — 线性时间复杂度
function printAllElements(arr) {
for (let i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
}
循环遍历数组，每多一个元素，循环多执行一次，时间复杂度是 O(n)。
🐢🐢 示例 3：O(n²) — 平方时间复杂度
function printPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
console.log(arr[i], arr[j]);
}
}
}
两个嵌套循环，每多一个元素，内层循环就执行 n 次，整体执行次数是 n * n，时间复杂度是 O(n²)。
🦅 示例 4：O(log n) — 对数时间复杂度（折半查找）
function binarySearch(arr, target) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
每次循环都将查找范围缩小一半，执行次数与数据规模增长的对数成正比，时间复杂度是 O(log n)。
💾 什么是空间复杂度？
空间复杂度指的是算法在执行过程中，除了输入数据本身外，需要占用多少额外的内存空间。
打个比方：
你写一封信，如果只写一句话，纸张占用很少；如果写很多内容，纸张自然也要多。这里的纸张就是空间，空间复杂度帮我们衡量占用的内存空间增长情况。
空间复杂度也是用大O表示法：O(1)、O(n)、O(n²)、O(log n) 等，下面用代码帮你理解。
📦 示例 1：O(1) 空间复杂度
function sumTwoNumbers(a, b) {
return a + b;
}
只用到了固定的两个变量，空间不随输入数据变化，空间复杂度是 O(1)。
📦 示例 2：O(n) 空间复杂度
function createArray(n) {
let arr = [];
for (let i = 0; i < n; i++) {
arr.push(i);
}
return arr;
}
随着 n 变大，创建的数组也变大，额外空间与输入规模成正比，空间复杂度是 O(n)。
📦 示例 3：O(n) 递归调用的空间复杂度
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
递归调用时，每一次函数调用都会在调用栈开辟空间，空间复杂度与递归深度成正比，这里是 O(n)。
🛠 如何分析复杂度？
通常分析算法时，重点关注最耗时的操作或者占用最多空间的结构。
举个生活场景：
如果你找钥匙在桌子上随便摸，那就像是 O(n)；如果你只看桌上固定一个地方，那就是 O(1)。
🧾 小节总结
- 时间复杂度度量的是算法运行时间随输入规模的变化趋势
- 空间复杂度度量的是算法运行过程中额外内存使用随输入规模的变化趋势
- 常见复杂度有 O(1)、O(n)、O(n²)、O(log n)，不同算法的复杂度差异巨大，影响程序性能
❓ 知识问答（Q&A）
Q：时间复杂度为什么不用具体时间单位？
A：时间复杂度关注的是算法增长趋势，具体时间因硬件和环境不同而异，使用大O符号更通用。
Q：递归一定会导致高空间复杂度吗？
A：不一定，尾递归可以被优化减少空间使用，但普通递归会因为调用栈增长导致空间复杂度较高。
🎉 恭喜你已经掌握 时间复杂度、空间复杂度、基本算法分析 技能啦！