【译】大O的友好指南

原文链接：https://medium.com/@daily_javascript/a-friendly-guide-to-big-o-ea781c5f68f0

算法复杂度

并不是每个公司在面试的时候都会问关于算法复杂度大O的问题，但是如果你想要到Facebook、Google或Amazon这样的公司工作的话，这是你必须要了解的知识。如果你没有很好的数学功底，那么你去看课本上关于大O的概念的话将会是一场灾难。

1
2

Let T(n) = the number of operations performed in an algorithm as a function of n. 
T(n) = O(f(n)) if and only if there exists two constants, n0 > 0 and c > 0, and a function f(n) such that for all n > n0, cf(n) ≥ T(n).

那么我们就一起来学习一下它的数学证明吧。开个玩笑，实际上证明要比概念复杂得多（译者：不会就直说嘛）。

回想一下，你是否曾经接受过这样的任务，为了完成它，你需要按照指定的步骤，一步一步来执行。在计算机科学中，这一系列指定的步骤被称为算法。

在现实生活中，我们为了完成一项任务，往往会寻找更好的办法：更快、更便宜、或者更明确的方法。算法也是一样，我们常常需要更好的算法来实现。但是我们怎么知道哪种算法对计算机而言是更好的呢？

一个比较直观的方法就是，选择不同算法之中，完成同一项任务用时最短的那个，也就是我们常说的运行时间最短的。不幸的是，我们没有办法精确的比较出哪个算法的运行时间更短，因为它受很多因素的影响。

例如：

写算法所用的语言
相同语言的版本差异
计算机硬件差异，每次读取数据的大小

我们能做的是通过计算算法从开始到完成一共做了多少步工作来近似的比较两个算法的运行时间。所以我们应该做出一些假设，而不管每个人使用的硬件和语言的差异，找到一个公认的方法来比较不同算法解决问题的能力。

假设1：

计算机每次从上到下读取一个步骤

假设2：

定义变量、调用函数、逻辑对比以及所有的算术运算都被当成一个步骤

假设3：

内存是无限大的，而且访问任何位置的数据所消耗的时间是一样的

做出了上面的假设之后，我们来看一个简单的例子：

function m(a, b) {
    ans = 1
    
    while(b > 0) {
        ans = ans * a
        b = b - 1
    }
    return ans
}

这个算法先定义了一个变量，这是一个步骤；然后开始了循环，这是三步（比较、乘法、减法）。最后返回变量，这也是一个步骤。所以这个算法的总步骤就是

1	2 + (3 * b)

如果b=100，这个算法就要进行302步，

如果b=1000，这个算法就要进行3002步，

如果b=10,000，这个算法就要进行30,002步。

可以看到，由于我们不需要精确的比较，所以数字2对结果的影响微乎其微。这就是为什么当我们计算大O的时候，你只需要关心影响最大的因素，而可以忽略常数以及影响较小的因素。我们再来看一个例子：

1	x + x^2 + x^3

你可以放心的忽略掉x和x²，因为它们没有x³对结果的影响大。

大O只是用来判断运行时间增加的速率，也叫作渐近分析。

所以我们已经知道了如何计算大O，但是我们怎么知道要选择哪些影响因素呢？我们需要尽可能大的输入，来忽略常数和低阶因素。大O表示的是最坏情况，这才是最有意义的比较结果。