时间复杂度和空间复杂度理解
空间复杂度和时间复杂度是算法分析中两个重要的概念，用于评估算法的性能。在前端 JavaScript 中，时间复杂度用于评估算法在最坏情况下的运行时间；空间复杂度描述了算法在执行过程中所需的内存空间的增长率，它包括算法所需的临时空间和输入数据所需的空间；理解时间复杂度和空间复杂度有助于选择更高效的算法和数据结构。
常见时间复杂度
-
O(1) - 常数时间复杂度
-
无论输入大小如何，算法所需的时间是固定的
例如：访问数组的某个元素。
const arr = [1, 2, 3]; console.log(arr[1]); // O(1)
-
-
O(log n) - 对数时间复杂度
-
每次操作都将问题规模减少一半
例如：二分查找
function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }
-
-
O(n) - 线性时间复杂度
-
随着输入规模的增加，运行时间线性增加
例如：遍历数组
function sum(arr) { let total = 0; for (let num of arr) { total += num; // O(n) } return total; }
-
-
O(n log n) - 线性对数时间复杂度
-
通常出现在高效的排序算法中，如归并排序和快速排序
function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } function merge(left, right) { const result = []; while (left.length && right.length) { if (left[0] < right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } return result.concat(left, right); }
-
-
O(n^2) - 平方时间复杂度
-
通常出现在嵌套循环中
例如：冒泡排序或选择排序
function bubbleSort(arr) { const n = arr.length; for (let i = 0; i < n; i++) { for (let j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; }
-
-
O(2^n) - 指数时间复杂度
-
输入大小增加时，运行时间以指数方式增加，通常出现在解决组合问题的递归算法中
function fibonacci(n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) }
-
常见空间复杂度
分析空间复杂度时，需要考虑以下几个方面：
- 基本数据类型：原始类型（如数字、字符串、布尔值）占用固定大小的内存。
- 数据结构：使用的数组、对象等数据结构会影响空间复杂度。例如，数组的大小和对象的属性数量会直接影响所需的内存。
- 递归：递归调用时，每次调用都会在调用栈中占用一定的空间，因此递归的空间复杂度通常与递归的深度有关。
- 辅助空间：在某些算法中可能会使用额外的存储空间（例如，临时数组、哈希表等），这部分空间也需要计算在内。
-
O(1)：常数空间复杂度。算法所需的空间不随输入规模而变化
-
在数组中查找元素而不使用额外的存储空间
function containsDuplicate(arr) { // 使用两个嵌套循环，但不使用额外的数组或对象 for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { if (arr[i] === arr[j]) { return true; // 找到重复元素 } } } return false; // 没有找到重复元素 } // 示例用法 const numbers = [1, 2, 3, 4, 5, 1]; console.log(containsDuplicate(numbers)); // 输出: true- 空间复杂度 O(1)：这个函数只使用了几个基本的变量（
i和j），不依赖于输入数组的大小，因此其空间复杂度为 O(1)。 - 时间复杂度：虽然这个例子在时间复杂度上是 O(n²)，但在空间上它并没有使用额外的空间。
- 空间复杂度 O(1)：这个函数只使用了几个基本的变量（
-
-
O(n)：线性空间复杂度。算法的空间需求与输入规模成正比
-
数组反转
// 空间复杂度：O(n)，因为需要一个新的数组来存储反转后的结果 function reverseArray(arr) { let reversed = []; for (let i = arr.length - 1; i >= 0; i--) { reversed.push(arr[i]); } return reversed; } -
递归求和
// 空间复杂度：O(n)，因为每次递归调用都会占用栈空间，最多会有 n 层 function sum(n) { if (n === 0) return 0; return n + sum(n - 1); }
-
-
O(n^2)：平方空间复杂度。常见于需要二维数据结构（如矩阵）的情况
-
输入大小增加时，运行时间以指数方式增加，通常出现在解决组合问题的递归算法中
function fibonacci(n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n) }
-
如何计算或者判断时间复杂度和空间复杂度？
如何计算时间复杂度：
- 识别基本操作：
- 确定算法中最频繁执行的操作（例如，循环、递归）。
- 分析控制结构：
- 循环：每个循环的复杂度通常是O(n)，其中n是循环次数。
- 嵌套循环：外层循环为O(n)，内层循环也为O(n)，则总复杂度为O(n²)。
- 递归：使用递归树或主定理进行分析。
- 简化表达：
- 忽略常数项和低阶项，保留最高阶项。
示例：
// 时间复杂度 O(n)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
// 时间复杂度 O(n^2)
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}
如何计算空间复杂度：
- 固定空间：
- 计算算法中使用的固定大小的变量、常量和输入输出。
- 动态空间：
- 计算依赖于输入规模的额外空间（如数组、对象、递归栈等）。
- 总空间：
- 将固定空间和动态空间相加，得出总空间复杂度。
示例：
// 空间复杂度 O(1)
function findMax(arr) {
let max = arr[0]; // 使用一个额外的变量
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 空间复杂度 O(n)
function createCopy(arr) {
let copy = []; // 新数组，空间复杂度O(n)
for (let i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
return copy;
}