8种大 O 表示法的 JavaScript 描述
站长
· 阅读数 2
大 O 简介
英文名：Big O notation
大 O 表示法是一种用于描述算法执行时间的渐进复杂性的数学表示方法。它指示了算法的运行时间如何随输入规模的增加而增长。
前端（JS）开发者为什么需要学习大 O?
- 性能优化
- 数据结构选择
- 避免低效
- 面试与团队协作
- 更好的库性能
大 O 归纳
| 时间复杂度 | 描述 | 示例 |
|---|---|---|
| O(1) | 常数-时间复杂度 | 访问数组中的元素 |
| O(log n) | 对数-时间复杂度 | 二分搜索 |
| O(n) | 线性-时间复杂度 | 遍历一个数组 |
| O(n log n) | 线性对数-时间复杂度 | 快速排序、归并排序 |
| O(n^2) | 平方-时间复杂度 | 嵌套循环遍历二维数组 |
| O(n^k) | 多项式-时间复杂度 | 多项式计算 |
| O(2^n) | 指数-时间复杂度 | 组合问题 |
| O(n!) | 阶乘-时间复杂度 | 排列和组合问题 |
图表示
难度分析
编程时不同的大 O 算法，编程的体感是不同的：
| 评价 | 时间复杂度 |
|---|---|
| 优秀/最佳 | O(1) |
| 好 | O(log n) |
| 公平 | O(n) |
| 坏 | O(n log n) |
| 可怕/最差 | O(n^2), O(2^n), O(n!) |
O(1)
执行时间与输入规模无关。O(1) 通常用于描述单个操作的时间复杂度，而不考虑一系列操作的总体复杂度。
- 基础数学运算
const a = 10;
const b = 20;
const result = a + b; // 无论操作数的值如何，基本的数学运算操作通常是常数时间。
- 数组访问、对象属性访问、索引操作
const array = [1, 2, 3, 4, 5];
const element = array[2]; // 无论数组有多大，访问单个元素的时间是常数。
const person = { name: "Alice", age: 30 };
const name = person.name; // 无论对象有多少属性，访问属性的时间是常数。
const array = [1, 2, 3, 4, 5];
array[2] = 10; // 更新数组中的元素，时间是常数。
array.pop(); // 从数组末尾删除元素，时间是常数。
O(log n)
对数时间复杂度，通常用于描述算法的执行时间随着输入规模 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; // 找到目标元素，返回其索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1; // 目标在左半部分
}
}
return -1; // 没有找到目标元素
}
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const targetValue = 7;
const result = binarySearch(sortedArray, targetValue);
if (result !== -1) {
console.log(`目标元素 ${targetValue} 在索引 ${result} 处找到。`); // 目标元素 7 在索引 3 处找到。
} else {
console.log(`目标元素 ${targetValue} 未找到。`);
}
二分搜索每次迭代都会将搜索范围缩小为原来的一半。
O(n)
O(n) 表示线性时间复杂度，意味着算法的执行时间与输入规模 n 成正比。
- 线性搜索
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // 找到目标元素，返回其索引
}
}
return -1; // 没有找到目标元素
}
const array = [10, 20, 30, 40, 50, 60, 70, 80];
const targetValue = 50;
const result = linearSearch(array, targetValue);
if (result !== -1) {
console.log(`目标元素 ${targetValue} 在索引 ${result} 处找到。`); // 目标元素 50 在索引 4 处找到。
} else {
console.log(`目标元素 ${targetValue} 未找到。`);
}
线性搜索遍历数组中的每个元素，直到找到目标值或遍历完整个数组。由于每个元素都可能需要检查一次，所以时间复杂度是 O(n)，其中 n 是数组的长度。
O(n log n)
O(n log n) 表示线性对数时间复杂度，通常出现在许多高效的排序算法中，如快速排序和归并排序。
- 归并排序
function mergeSort(arr) {
if (arr.length <= 1) {
return arr; // 基本情况：如果数组长度为 0 或 1，直接返回
}
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}
const unsortedArray = [6, 5, 3, 1, 8, 7, 2, 4];
const sortedArray = mergeSort(unsortedArray);
console.log("排序后的数组:", sortedArray); // 排序后的数组: [
1, 2, 3, 4,
5, 6, 7, 8
]
归并排序的时间复杂度是 O(n log n)。它将数组分成较小的部分，然后递归地合并这些部分以生成排序后的结果。
O(n^2)
平方时间复杂度，通常出现在一些嵌套循环或对数组进行双重遍历的算法中。这种复杂度意味着算法的执行时间与输入规模 n 的平方成正比。
- 选择排序
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
// 交换元素
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log("排序后的数组:", sortedArray); // 排序后的数组: [ 11, 12, 22, 25, 64 ]
选择排序的时间复杂度是 O(n^2)。它通过遍历数组中的每个元素，找到未排序部分的最小元素，然后将其放在已排序部分的末尾。
O(n^k)
| 时间复杂度 | 描述 | 示例 |
|---|---|---|
| O(n^2) | 二次时间复杂度 | 二维数组的嵌套遍历 |
| O(n^3) | 三次时间复杂度 | 三层嵌套循环问题 |
| O(n^k) | k 次时间复杂度 | 高次幂问题，其中 k 较大 |
- O(n^2) 示例
function nestedLoopExample(n) {
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
console.log(`i: ${i}, j: ${j}`);
}
}
}
nestedLoopExample(3); // 一个嵌套循环示例，n=3
/*
i: 1, j: 1
i: 1, j: 2
i: 1, j: 3
i: 2, j: 1
i: 2, j: 2
i: 2, j: 3
i: 3, j: 1
i: 3, j: 2
i: 3, j: 3
*/
O(2^n)
- 子集生成
O(2^n) 表示指数时间复杂度，通常出现在某些组合问题中，其中算法的执行时间随着输入规模 n 的指数方式增长。这种复杂度是非常高的，因为它意味着算法的性能在输入规模增加时迅速恶化。
function generateSubsets(arr) {
const subsets = [];
const n = arr.length;
for (let i = 0; i < (1 << n); i++) {
const subset = [];
for (let j = 0; j < n; j++) {
if ((i & (1 << j)) !== 0) {
subset.push(arr[j]);
}
}
subsets.push(subset);
}
return subsets;
}
const inputArray = [1, 2, 3];
const allSubsets = generateSubsets(inputArray);
console.log("所有可能的子集：", allSubsets);
// 所有可能的子集： [
// [], [ 1 ],
// [ 2 ], [ 1, 2 ],
// [ 3 ], [ 1, 3 ],
// [ 2, 3 ], [ 1, 2, 3 ]
// ]
使用了位运算和嵌套循环来生成所有可能的组合。由于每个元素都可以选择或不选择，存在 2^n 种可能的组合。
O(n!)
O(n!) 表示阶乘时间复杂度，通常出现在排列和组合问题中，其中算法的执行时间与输入规模 n 的阶乘成正比。这种复杂度非常高，因为阶乘增长非常快。
- 生成排列
function generatePermutations(arr) {
const permutations = [];
const n = arr.length;
function permute(arr, start) {
if (start === n) {
permutations.push([...arr]);
return;
}
for (let i = start; i < n; i++) {
[arr[start], arr[i]] = [arr[i], arr[start]];
permute(arr, start + 1);
[arr[start], arr[i]] = [arr[i], arr[start]]; // 恢复原始顺序
}
}
permute(arr, 0);
return permutations;
}
const inputArray = [1, 2, 3];
const allPermutations = generatePermutations(inputArray);
console.log("所有可能的排列：", allPermutations);
// 所有可能的排列： [
// [ 1, 2, 3 ],
// [ 1, 3, 2 ],
// [ 2, 1, 3 ],
// [ 2, 3, 1 ],
// [ 3, 2, 1 ],
// [ 3, 1, 2 ]
// ]
使用了递归和循环来生成排列，对于一个长度为 n 的数组，存在 n! 种可能的排列。因此，算法的时间复杂度是 O(n!)。
小结
在开发过程中，能了解问题规模，确定不同的规模的事情的使用不同的算法。大 O 表示算法执行时间渐进复杂性的数学表示方法。使用大 ） 进行算法的效率和性能分析。总体上分为：常数、对数、线性/非线性、平方、多项式、指数、阶乘等，并在 JavaScript 中实现最简单的算法， 其中 O(1) 最为简单，从 O(n log n) 开始变得复杂，编程体感也开始变差。