大O符号速查表

本文是我从希腊密码学/区块链博士候选人Dionysis "dionyziz" Zindros的一篇关于算法复杂度的精彩文章中整理的笔记。我强烈推荐这篇文章给所有对算法复杂度感兴趣的人，即使是第一次接触这个概念。如果您已经对时间复杂度有所了解，希望这篇文章能帮助您重温一下。

如今，随着用户数量的增长，可扩展性可能是最常用的术语之一。虽然我们可以搭建基础设施来应对这种负载，但我们也需要编写相应的代码来实现这一目标。为了分析代码并了解其效率，我们使用大O表示法。它还可以帮助我们了解代码在负载增加时的性能表现。最后，我们还可以使用大O表示法来比较不同的算法。

计数说明

一个函数需要若干指令才能运行，并且可能会根据编写该函数的语言或运行该函数的架构而延迟执行。

let element = list[0];

for (let i = 0; i < n; ++i) {
  if (list[i] >= element) {
    element = list[i];
  }
}

上述函数需要4 + 2n指令才能运行，我们可以将其分配给一个变量f(n)。（你能猜到我们是怎么想到这个方法的吗？）

最坏情况分析

最坏情况分析术语指的是函数将运行它能够运行的所有指令的情况，也就是最坏的情况。

渐近行为

由于我们需要考察的是函数的总体性能，而不是它在特定架构或语言上的性能，因此我们通过舍弃增长缓慢的项来简化指令数量。所以，函数f(n) = 4 + 2n变为f(n) = n。函数仍然以与之前相同的速度增长，但看起来简洁得多。

复杂

我们将算法最坏情况下的渐近行为称为复杂度，并将其记为Θ。因此，函数的复杂度f(n) = 4 + 2n为Θ(n)，读作θ(n)。

大O符号

当我们开始分析复杂函数时，会发现有时很难确定最坏情况下的具体操作步骤。不过，我们可以修改算法，使其性能略微恶化（当然，这只是我们想象中的恶化），从而找到比实际情况更糟糕的情况。如果我们确信得到的复杂度确实更糟，就可以将其表示为“ O(Θ(n))n 的 θ 的大 O 符号”。例如，这O(n^2)意味着我们的函数渐近性能不会比 n² 更差。

上限

O(n^2)是实际时间复杂度的上界。虽然这没错，但它也可能就是实际时间复杂度。因此，这给了我们一个紧界。如果我们确定 Θ(n) 肯定不是 Θ(n)但 Θ ( O(n)n )是O(n^2)...o(n^2)Θ(n)O(n)o(n^2)

下限

虽然我们已经找到了上限或最坏情况，但找到最佳情况也很有用。下限告诉我们函数的复杂度不能超过这个值。我们用 Ω（读作大写 omega）表示紧下限，用 ω 表示非紧下限。

对数

对数运算是将一个数缩小很多倍。同样地，平方根是平方运算的逆运算，对数是指数运算的逆运算。

某些算法在每次迭代中都会对输入进行拆分，这类算法往往O(log(n))复杂度较高，但效率通常也最高。例如快速排序和归并排序算法。

示例

O(1)

function getLast (items) {
  return items[items.length-1]; 
};

在）

function findIndex (items, match) {
  for (let i = 0, total = items.length; i < total; i++) {
     if (items[i] == match) {
        return i;
     }
  }

  return -1;
};

O(n^2)

function buildSquareMatrix (items) {
  let matrix= [];

  for (let i = 0, total = items.length; i < total; i++) { 
    matrix[i] = [];

    for (let j = 0, total = items.length; j < total; j++) {
      matrix[i].push(items[j]);
    }
  }
  return matrix;
};

O(log(n))

 function quickSort (list) {
  if ( list.length < 2) {
    return list;
  }

  let pivot = list[0];
  let left = []; 
  let right = [];

  for (let i = 1, total = list.length; i < total; i++ ){
    switch (true){
      case (list[i] < pivot):
        left.push( list[i] );
        break;
      case (list[i] >= pivot):
        if( list[i] ) {
          right.push( list[i] );
        }
        break;
    }
  }

  return [].concat(quickSort(left), pivot, quickSort(right));
};