漫画：经典谷歌面试题“扔鸡蛋”，看看你会做吗？
https://mp.weixin.qq.com/s/NugGnNX4Vv3SNhQrmzjF-A

在近三天内修改的文章随机排序：MODIFY_DATE + RAND() * 4

算法复杂度（Algorithmic complexity）

什么是算法复杂度_icolakele的博客-CSDN博客_算法的复杂度

就是衡量程序执行效率的度量方法。衡量算法的好坏，不仅要看程序执行所需的时间，还要看程序用到的计算资源，比如内存资源。

事实上，算法复杂度包括时间复杂度(Time complexity)和空间复杂度(Space complexity)。我们平时说的算法复杂度，一般都是在说算法的时间复杂度。

时间复杂度

理论上讲，程序执行消耗的时间是无法事先估算的，那如何计算时间复杂度呢？换个思路，程序执行时必然有一定的步骤，不防假设执行每个步骤所需要的时间为t，t具体是什么值并不重要，然后只需要计算一个程序执行所需要的步骤，最终以步骤数来衡量算法时间复杂度。

理论上讲，程序执行消耗的时间是无法事先估算的，那如何计算时间复杂度呢？换个思路，程序执行时必然有一定的步骤，不防假设执行每个步骤所需要的时间为t，t具体是什么值并不重要，然后只需要计算一个程序执行所需要的步骤，最终以步骤数来衡量算法时间复杂度。

举个例子，计算1+2的复杂度是多少呢？

a = 1
b = 2
sum = a + b

一共有3个步骤，不防记作O(3)，其实O(3) = O(1)。
计算正整数n的阶乘呢？

factorial = 1
for i = 1 to n
factorial = i * factorial

第一行执行1次，第二行执行n次 ，第三行执行n次，一共执行2n + 1次。不防记作O(2n + 1)。其实O(2n + 1) = O(n)。

大 O 表示法

现在可以很自然的引入大O表示法了(Big O notation)。为什么用O呢？其实这里的O源自短语函数的阶数(Order of the function)。
如果还记得高数中等价无穷小和等价无穷大的概念的话，就很容易理解大O表示法了。

f(x) = 3x³ + 2x +10

不难理解，当x趋于∞时，对f(x)值变化影响最大的是x³，那么我们就可以说f(x)和x³是等价无穷大的。因此，常数次执行步骤的算法复杂度统称为O(1)，这也是为什么前面我说O(3) = O(1)。类似的，O(2n + 1) = O(n)。
计算算法时间复杂度时，我们只需要关心对结果影响最大的那一项，也就是直接找到计算结果等价无穷大最简洁的表示方法。因此我们可以推导出O(f(x)) = O(x³)。
大O表示法其实是在描述一个算法在遇到最糟糕的情况时执行的效率。
想象一下唐伯虎点秋香场景，从n个蒙面女生中点中秋香，最好的情况是第一次就点中秋香，最坏的情况则需要n次。这里，我们就认为找秋香的算法复杂度是O(n)。
有了以上的基础，我们就很容易理解下面这些常见的算法复杂度了。