代码运行速度差异巨大，原因何在？答案是：大O表示法——程序员评估算法效率的利器。本文将简明扼要地解释大O表示法。
什么是大O表示法？
大O表示法描述算法性能随输入规模增长变化的趋势。它衡量的是，当输入数据量增加时，算法执行时间如何变化。
常见的大O复杂度
O(1) - 常数时间
最佳性能。无论输入大小如何，执行时间恒定不变。
function getfirstelement(array) {
return array[0]; // 始终只有一个操作
}
O(log n) - 对数时间
通常出现在每次将问题规模减半的算法中，例如二分查找。
function binarysearch(sortedarray, target) {
let left = 0;
let right = sortedarray.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (sortedarray[mid] === target) {
return mid;
} else if (sortedarray[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
O(n) - 线性时间
性能随输入大小线性增长。需要遍历每个元素一次的算法通常属于此类。
function findmax(array) {
let max = array[0];
for (let i = 1; i < array.length; i++) {
if (array[i] > max) max = array[i];
}
return max;
}
O(n log n) - 线性对数时间
高效排序算法（如归并排序和快速排序）的典型复杂度。
function mergesort(array) {
if (array.length <= 1) return array;
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return merge(mergesort(left), mergesort(right));
}
function merge(left, right) {
let 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²) - 平方时间
嵌套循环的常见复杂度。性能随输入大小的平方增长，效率低下。
function bubblesort(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
return array;
}
编写高效代码的实用技巧
- 避免嵌套循环： 使用哈希表查找代替嵌套迭代；考虑排序是否能简化问题。
- 选择合适的数据结构： 数组用于快速访问有序数据；哈希表用于快速查找；二叉树用于维护排序数据。
- 空间与时间的权衡： 有时增加内存使用能显著提高时间效率；缓存常用值。
常见陷阱
-
隐藏的循环： 看似O(n)，实际可能为O(n²)
// 看似 O(n)，实际上是 O(n²) array.forEach(item => { const index = anotherarray.indexOf(item); // indexOf 是 O(n) }); -
循环中的字符串拼接： 低效的字符串拼接方式。
实际应用
了解大O表示法能帮助您：
- 选择合适的算法和数据结构
- 优化性能瓶颈
- 做出更好的架构决策
- 通过技术面试
其他资源
- 《算法导论》- 权威学术资源
- 大O速查表 - 常用操作快速参考
- Visualgo - 算法和数据结构可视化工具
结论
大O表示法看似学术，实则编写高效代码的实用工具。掌握这些基础知识，将有助于编写更高效的算法。
您在算法优化方面有什么经验？欢迎在评论区分享您的想法和问题！
