快速理解大 O 复杂度

有人说你也是算法的门外汉怎么就胆敢写文章来教别人了呢？谁说写文章是为了教别人呢？我又不是老师，写文章算是对自己的一个总结，从自己学到自己写出来，假装会有读者来看，我的责任是让对方能看懂，这就足够了。

算法入门的时候几乎所有书籍和博客都会说，用大 O 来表示算法复杂度。确实，衡量一个东西的好坏需要一个标准或者规范，大写的 O 就是这个规范。算法的复杂度有两种定义：时间复杂度和空间复杂度。这两者都是用大 O 来表示。在大多数时候，我们更关注的是时间复杂度，空间上正常是较为宽裕的，一个算法很难产生堆栈的溢出。

初学者一眼看到 O(logn)之类的符号时，曾经被高等数学支配的恐惧就油然而生，心理上首先就破防了。大可不必，心理的畏惧会让我们一事无成。其实一共用来表示的符号只有这几种：O(1)，O(n)，O(n^2)，O(logn)，O(nlogn)。剩下的就是分析什么情况下是哪一种复杂度，复杂度的表示有什么用呢？在写算法的时候几乎没用，但在和别人交流算法的时候有用，可以理解为算法交流的通用语言。

现在来解释一下分别是什么场景：

O(1)

无论什么输入下，这个算法只需要执行固定的行数。这一般出现在值交换这样的简单算法上，因为一旦涉及到数组、列表之类的处理，长度未定所需执行的行数肯定也未定。

O(n)

这就很好理解了，比如遍历一个列表，列表有多长就要循环多少次，这个 n 就代表长度。

O(n^2)

正常情况下，这是比较糟糕的情况。因为有了指数，所需要的执行的行数会指数级上升，长度 n 越长，所需承担的时间成本最终会高的难以想象。循环嵌套循环就会产生 n^2，再嵌套一层就是 n^3，因为 n 个元素每个都要在下层循环 n 次，所以是 n * n。

O(logn)

可能很多人不是被前面的几个吓到，而是这个。log 在数学里是对数，应该是高中数学，可能现在已经是初中了。有指数，相对应的就肯定有对数，这里默认是 log2^n，底数为 2 的对数，简写为 logn。假如 log2^n = x，那 x^2 = n，这是一个相互转换的简单例子。什么场景下会是 logn 的复杂度呢，就是每一步执行都会减少一半的元素，比如二分查找，每次从中间取值之后都会定位到某一个半区，从而另一半的元素就不是我们的目标区域，直接范围变成原来的 1/2，这便是对数时间。

O(nlogn)

有了上面的基础，这个就很好理解了。还是说二分查找，查询一个数组需要 O(logn)，那查询 n 个数组就是 O(nlogn)了。

对大 O 的恐惧是不是有所减少呢？