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

为什么使用大 O 表示法？

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

示例：求和

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

选项 1：使用循环

function addUpTo(n) {
    let total = 0;
    for (let i = 1; i 




  
  
  选项 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 printAllPairs(n) {
    for (var i = 0; i 



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


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




function countUpAndDown(n) {
    console.log("Going up!");
    for (var i = 0; i = 0; j--) {
        console.log(j);
    }
    console.log("Back down. Bye!");
}





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


  
  
  简化分析


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

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

空间复杂度

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

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

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

示例

function sum(arr) {
    let total = 0;
    for (let i = ; i 



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

对于创建新数组的函数：



function double(arr) {
    let newArr = [];
    for (let i = 0; i 



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


  
  
  结论


Big O Notation 提供了一个框架，用于以独立于硬件和具体实现细节的方式分析算法的效率。理解这些概念对于开发高效的代码至关重要，尤其是随着数据规模的增长。通过关注性能如何扩展，开发人员可以就在其应用程序中使用哪些算法做出明智的选择。