大 O 表示法：简单指南-js教程-PHP中文网

Big O Notation: A Simple Guide

大 O 表示法是一个数学概念，用于描述算法随着输入大小的增长而在时间和空间方面的性能或复杂性。它帮助我们了解算法的运行时间如何随着输入的增加而增加，从而可以对不同算法进行更标准化的比较。

为什么使用大 O 表示法？

在比较算法时，仅依赖执行时间可能会产生误导。例如，一种算法可能会在一小时内处理大量数据集，而另一种算法可能需要四个小时。但是，执行时间可能会根据计算机和其他正在运行的进程而有所不同。相反，我们使用 Big O 表示法来关注执行的操作数量，这提供了更一致的效率衡量标准。

示例：求和

让我们探索两种计算从 1 到 n 的所有数字之和的方法：

选项 1：使用循环

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

登录后复制

选项 2：使用公式

function addUpTo(n) {
    return n * (n + 1) / 2;
}

登录后复制

分析复杂性

在选项 1 中，如果 n 为 100，则循环运行 100 次。相反，选项 2 始终执行固定数量的运算（乘法、加法和除法）。因此：

选项1是O(n)：时间复杂度随n线性增长。
选项 2 为 O(1)：无论输入大小如何，时间复杂度保持不变。

免责声明

虽然选项2涉及三种运算（乘法、加法、除法），但我们关注的是Big O分析的总体趋势。因此，我们不是将其表示为 O(3n)，而是将其简化为 O(n)。同样，O(n 10) 简化为 O(n)，O(n^2 5n 8) 简化为 O(n^2)。在大 O 表示法中，我们考虑最坏的情况，其中最高阶项对性能的影响最大。

除了上面列出的常见复杂度之外，还有其他形式的表示法，例如表示为 O(log n) 的对数时间复杂度。

什么是大 O 表示法？

大 O 表示法允许我们根据输入大小来形式化算法运行时间的增长。我们不关注特定的操作计数，而是将算法分为更广泛的类别，包括：

恒定时间：O(1) - 算法的性能不随输入大小而变化。
线性时间：O(n) - 性能随着输入大小线性增长。
二次方时间：O(n^2) - 随着输入大小的增加，性能呈二次方增长。

O(n^2) 的示例

考虑以下函数，它打印从 0 到 n 的所有数字对：

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

登录后复制

在这种情况下，函数有两个嵌套循环，因此当 nnn 增加时，操作数量呈二次方增加。对于 n= 2，有 4 次操作，对于 n=3，有 9 次操作，导致 O(n^2)。

另一个例子：向上和向下计数

function addUpTo(n) {
    return n * (n + 1) / 2;
}

登录后复制

乍一看，人们可能会认为这是 O(n^2)，因为它包含两个循环。然而，两个循环独立运行并随 n 线性缩放。因此，总体时间复杂度为 O(n)。

简化分析

分析代码复杂性的各个方面可能很复杂，但一些通用规则可以简化事情：

算术运算被视为常数时间。
变量赋值是常数时间。
访问数组（通过索引）或对象（通过键）中的元素是常数时间。
对于循环，复杂度是循环的长度乘以循环内部发生的事情的复杂度。

空间复杂度

虽然我们关注时间复杂度，但也可以使用 Big O 来计算空间（内存）复杂度。有些人在计算中包含输入大小，但仅关注算法所需的空间通常更有用本身。

空间复杂度规则（基于 JavaScript）：

大多数原始值（布尔值、数字等）都是常量空间。
字符串需要 O(n) 空间（其中 n 是字符串长度）。
引用类型（数组、对象）一般都是 O(n)，其中 n 是数组的长度或对象中键的数量。

示例

function printAllPairs(n) {
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
            console.log(i, j);
        }
    }
}

登录后复制

在此函数中，空间复杂度为 O(1)，因为无论输入大小如何，我们都使用恒定量的空间（两个变量）。

对于创建新数组的函数：

function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i < n; i++) {
        console.log(i);
    }
    console.log("At the top!\nGoing down...");
    for (var j = n - 1; j >= 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}

登录后复制

这里，空间复杂度是 O(n)，因为我们为一个新数组分配空间，该数组随着输入数组的大小而增长。