原文地址：https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

写在前面：经常看到用O(N)这样类似的标记来表达算法的复杂度，非计算机或数学专业的人可能不会太懂，翻到了一篇浅显易懂的文章来简单介绍一下。里头的例子虽然不是用的Javascript不过理解却并不复杂。需要注意的是我并不会逐字逐句的翻译，主要还是按照意思加入了一些我个人的理解，建议对照着原文阅读。

A beginner's guide to Big O notation

大写的O标记经常用在计算机科学中来表达一个算法的性能或者复杂度。尤其是它可以用来描述最坏的情况下，算法所需要的时间或者空间（比如内存或者硬盘空间）。

有时候看到O(N logN)之类的复杂标记可能许多人会弄不明白，希望在这篇文章可以帮助到你们。

作为一个程序员和数学家，我觉得最好的解释方法就是用一下实际的代码来帮助理解。下面我就按照从易到难的顺序来一一解释。

O(1)

O(1)用来描述一个算法执行时，不管输入的数据有多少，总是需要同样的时间或空间。

bool IsFirstElementNull(IList<string> elements)
{
    return elements[0] == null;
}

O(N)

O(N)用来描述一个算法执行时时间（或空间）随着输入的数据量而线性增长，下面这个例子就展示了，这个O标记总是会考虑到最坏的情况。可能在这个函数中的循环最开始就可以找到符合条件的string从而return，但是事件复杂度总会按照上限来记录。

bool ContainsValue(IList<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

O(N^2^)

这个表示算法的复杂度直接和输入数据量的平方成正比，通常这个主要见于数据的嵌套迭代，更多重的循环嵌套可能会出现复杂度为O(N^3^)，O(N^4^)等等。

bool ContainsDuplicates(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O(2^N^)

O(2^N^)用来表示随着数据量每增加一则算法的复杂度翻倍，这样的函数的复杂度曲线是呈指数增长的：一开始特别小，但是增长的速度越来越快。很典型的就是递归的斐波那契数列函数：

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

指数

指数解释起来就稍微有一点复杂了，这里我用一个比较常见的例子： 比如常见的二分查找，在排好序的情况下，通常我们选一个中间的数据，来和目标值比较，符合则返回true，比之大或者小的我们则同右侧或者左侧的数据重复一开始的步骤，不断缩小范围最终成功查找到。这样的复杂度我们通常描述为**O(log N)**，就如同指数的曲线一样，一开始会很陡峭，但随着数据的增多，复杂度反而慢慢趋于平缓，不会有特别大的增加。比如包含10个数字的数据量需要1秒来完成，包含100个数字的数据量需要2秒，包含1000个可能只需要3秒。翻倍的数据量对于复杂度的影响微乎其微，所以这也是为什么二分查找算法在面对大量的数据的时候特别有优势。

当然我这里的解释还是很基础的，稍微详细的内容可以查看维基百科关于*Big O notation和Logarithms*的解释。