初学者大 O 表示法：实用指南

有没有想过为什么有些代码运行得非常快，而其他代码却在爬行？输入大 O 表示法 - 开发人员用来讨论算法效率的秘密语言。让我们简单地分解一下。

什么是大 O 表示法？

大 O 表示法描述了代码的性能如何随着输入大小的增长而扩展。将其视为衡量当您给代码分配更多工作要做时需要多长时间。

常见的大O复杂性

O(1) - 恒定时间

性能的圣杯。无论您的输入有多大，操作所需的时间都是相同的。

function getFirstElement(array) {
    return array[0];  // Always one operation
}

O(log n) - 对数时间

通常出现在每次将问题一分为二的算法中。二分查找就是一个典型的例子。

function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (sortedArray[mid] === target) return mid;
        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 = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));

    return merge(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;
}

编写高效代码的实用技巧

1. 尽可能避免嵌套循环

   • 使用哈希表进行查找而不是嵌套迭代
   • 先考虑一下是否可以通过排序来解决你的问题

2. 选择合适的数据结构

   • 可快速访问的有序数据数组
   • 用于快速查找的哈希表
   • 用于维护排序数据的二叉树

3. 空间与时间的权衡

   • 有时使用更多内存可以显着提高时间复杂度
   • 缓存经常访问的值

常见陷阱

1. 隐藏循环

// Looks like O(n), actually O(n²)
array.forEach(item => {
    const index = anotherArray.indexOf(item);  // indexOf is O(n)
});

1. 循环中的字符串连接

// Poor performance
let result = '';
for (let i = 0; i < n; i++) {
    result += someString;  // Creates new string each time
}

// Better approach
const parts = [];
for (let i = 0; i < n; i++) {
    parts.push(someString);
}
const result = parts.join('');

实际应用

了解 Big O 可以帮助您：

• 选择正确的算法和数据结构
• 优化性能瓶颈
• 做出更好的架构决策
• 通过技术面试

其他资源

• 算法导论 - 综合学术资源
• Big O Cheat Sheet - 常用操作快速参考
• Visualgo - 可视化算法和数据结构

结论

大 O 表示法可能看起来很学术，但它是编写更好代码的实用工具。从这些基础知识开始，您将开始编写更高效的算法。

---

您在算法优化方面有什么经验？在下面的评论中分享您的想法和问题！

以上是初学者大 O 表示法：实用指南的详细内容。更多信息请关注PHP中文网其他相关文章！