“大O符号”到底是什么意思？

如果你是一名程序员，你很可能遇到过“大O表示法”这个术语。但它究竟是什么意思呢？

大O表示法用于描述程序或数据结构的计算复杂度。其基本含义是：执行某个操作需要多少步骤。“步骤”在此并非指CPU周期或程序中的代码行数，而是指任意长度固定的步骤，无论其大小如何。

我们先来看一个例子：检查一个元素是否在数组中。在 JavaScript 中，你可以这样实现：

function findInArray(array, element) {
    for(let i = 0; i < array.length; i++) {
        if(array[i] === element) {
            return true;
        }
    }
    return false;
}

你很容易就能看出这一点：循环内的所有操作都耗时恒定：通过索引访问数组元素并进行比较。我们将其定义为 1 个“步骤”。但由于循环的存在for，我们需要执行这些n操作。用大 O 表示法表示为：O(n)。

其他用大O符号描述的标准例子包括排序算法。以最简单的排序算法——冒泡排序为例，它的实现可以如下所示：

function bubblesort(array) {
    for(let i = 0; i < array.length; i++) {
        for(let j = 0; j < array.length - 1; j++) {
            if(array[j] > array[j + 1]) {
                let tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

对于数组中的每个元素，循环遍历整个数组，并在需要时交换元素。和之前一样，循环中的所有操作都是常量。然后我们有一个循环执行此n操作 次。但我们还有一个循环，它会执行第一个循环n次。因此，我们总共执行了次n操作n。用大O表示法表示：O(n*n) = O(n²)

但也有其他情况下，答案并非如此简单。例如，请看以下代码片段：

function mapAndFilter(x) {
    return x
        .map(n => n * 2)
        .filter(n => n > 0);
}

这个函数的复杂度是多少？是吗？

• O(1)？
• O(n)？
• O(n²)？
• 有点不一样？

正确答案是O(n)。为什么？虽然我们的代码本身是恒定的（没有直接循环），但执行其他函数也需要一些时间。在这种map情况下，浏览器会遍历所有元素并对它们调用该函数（因此这将是O(n)），filter这基本上与我们的 相同findInArray，所以也是O(n)。我们的函数加起来将有O(n+n) = O(2n)，但大 O 表示法不考虑常数因子，因此2会被省略，最终得到O(n)。

我认为这是一个很好的例子，说明你不仅要检查自己的代码，还要检查通过库或浏览器导入的代码。任何操作数据结构的算法都有其计算复杂度。如果你了解这一点，就可以编写复杂度尽可能低的代码。你还可以问自己：“我需要对数据结构执行哪些操作？是否存在复杂度更低的替代数据结构？”

这是关于常见数据结构及其内部工作原理系列文章的第一篇。如果您对这类文章感兴趣，请关注我，也欢迎留言告诉我您感兴趣的数据结构。