大 O 符号、时间和空间复杂度概述

目录：

目录：

• 大 O 符号
  • 运行时
  • 时间复杂度
  • 空间复杂度
• 符号
  • 线性：O(n)
  • 持续的：O(1)
  • 二次：O(n^2)
  • 阶乘：O(n!)
  • 对数：O(log N)
  • 对数线性：O(n log(n))
  • 指数：O(2^n)
• Big O 备忘单

大 O 符号

大 O 符号是一种数学符号，它描述当参数趋向于特定值或无穷大时函数的极限行为。

它将彻底改变你编写代码的方式。它有助于提高代码的可读性和可扩展性。

可读代码是可维护的代码。它易于阅读，并且包含有意义的变量、函数等名称。

可扩展代码指的是速度和内存。代码需要可扩展的原因在于我们不知道有多少用户会使用我们的代码。我们必须能够确定算法的解决方案，并权衡速度和内存成本。

Big O Notation 将以两种方式使用：

1. 对算法的时间复杂度（速度）进行分类。
2. 对算法的空间复杂度（内存）进行分类。

运行时

在计算机科学中，运行时（ runtime）或执行时间（execution time）是指计算机程序生命周期的最后阶段，在此阶段，代码以机器码的形式在计算机的中央处理器 (CPU) 上执行。换句话说，“运行时”是程序运行的阶段。

本质上，运行时间是算法运行的时间段。这是一个重要的术语，以后需要了解。

时间复杂度

时间复杂度是描述运行算法所需时间的计算复杂度。

在对算法的时间复杂度进行分类时，需要考虑许多优点和缺点：

• 最坏的情况是什么？

首先考虑最坏的情况，因为很难确定平均情况或最佳情况。

• 您应该使用什么数据结构？

有些符号专门用于某些数据结构。我将在下面的“符号”部分向您展示。下方还有一个Big O 速查表，它将向您展示哪些符号更适用于某些结构。

• 哪一个解决方案比另一个更好？

哪种结构具有更节省时间的表示法？哪种结构具有更节省内存的表示法？

• 您必须在空间和时间的利弊之间进行权衡。

大 O 用于确定算法的时间和空间复杂度。有些解决方案可能速度更快，但内存占用却更低，反之亦然。这取决于所提倡的路线。

空间复杂度

算法或计算机程序的空间复杂度是根据输入的特征解决计算问题实例所需的内存空间量。

空间复杂度是由变量、数据结构、分配等因素造成的。你创建的内容会占用空间。空间复杂度的确定方式与 Big O 确定时间复杂度的方式相同，符号如下，不过本博客不会深入探讨空间复杂度的计算。

符号

符号的顺序是从最好到最差的：

1. 持续的：O(1)
2. 对数：O(log N)
3. 线性：O(n)
4. 对数线性：O(n log(n))
5. 二次：O(n^2)
6. 指数：O(2^n)
7. 阶乘：O(n!)

在本博客中，我将仅讨论常数、线性和二次符号。其他符号将包含对特定数据结构和算法的描述。

持续的：O(1)

常量表示法非常出色。就速度而言，函数的运行时间始终相同。即使输入增加，函数仍会在相同的时间内输出相同的结果。

假设我们有一个数组：

  let array = ['A', 'B', 'C', 'D'];

数组是包含元素集合的有序数据结构。

关联数组是由键值对组成的无序数据结构。

  let associativeArray = {message: "hello", name: "Ethan"};

当访问这些数据结构中的任一个元素时，Big O 始终是恒定时间。

  array[2]
  // => C

  associativeArray.message
  // => hello

这是因为不需要搜索任何元素。元素的位置可以通过其索引或标识符来知道。

对数：O(log N)

二叉搜索树使用对数符号。二叉树是一种树形数据结构，由最多包含两个子节点的节点组成。

在二叉搜索树中，没有重复项。节点的左子树包含键值小于其父节点值的子节点。右子树则相反，其子节点的值大于其父节点的值。

线性：O(n)

随着输入的增加，完成函数所需的时间也会增加。运行时间会随着输入规模的增加而增长。此外，n可以是任意值，例如x、o等等。

O(n)数组上的循环就是一个例子：

  let group = ['jack', 'jolene', 'ethan', 'ali', 'logan', 'bob'];

  function findEthan(array) {
    for (let i = 0; i < array.length; i++){
      if (array[i] === 'ethan'){
        console.log("I found him!");
        break;
      }
    }
  }

  findEthan(group);

函数的输入规模可能会急剧增加。如果人群中有 500 人怎么办？函数的执行时间会更长，尤其是当我的名字位于数组的最后一个元素时。

你能想象输入量更大吗？比如说 10,000？执行算法所需的时间取决于输入量的大小。输入量越大，算法长度也越长。这就是线性符号。

二次：O(n^2)

二次符号是线性符号，但有一个嵌套循环。

  function something(array) {
    for(let h = 0; h < array.length; h++) {
      for(let i = 0; i < array.length; i++) {
        // console.log('')
      }
    }
  }

我们不知道输入的大小，并且有两个for循环，其中一个嵌套在另一个循环中。

对数线性：O(n log(n))

Quicksort算法采用对数线性表示法，具有最佳的时间复杂度。

指数：O(2^n)

网上关于指数符号在现实世界中的应用的例子并不多。

阶乘：O(n!)

这种表示法绝对是最糟糕的。当你对每个输入都进行嵌套循环时，这种表示法就被判定为阶乘。

Big O 备忘单

• Big O 备忘单

该备忘单显示了由数据结构和算法组成的列表的空间复杂度。