讨论算法复杂度，不妨从某个语句的执行次数开始。 例一
先来看一个例子，这里有一个函数，里面执行的操作是 a = 1，那么可以算一下这段代码的计算次数，我们知道这里一共只执行了一次计算。 Python3
def func(): a = 1例二
换一个复杂一点的情况，下面这个例子里我们加了一个循环，所以显然这里进行了 10 次计算。 Python3
def func(): for i in range(10): a = 1再复杂一点，我们再加一个循环，这里一共执行了 10 × 10 = 100 次计算。 Python3
def func(): for i in range(10): for j in range(10): a = 1再把上述例子改难一点，把第二重循环的起点变成 i。 Python3
def func(): for i in range(10): for j in range(i, 10): a = 1
我们在前一节最后留下了这样的代码： Python3
def func(): for i in range(10): for j in range(i, 10): a = 1在这里 10 是一个已经给定的值，很多情况下这个数是被一个变量代替的，比如 n。那么如果把 10 改成 n 的话： Python3
def func(): for i in range(n): for j in range(i, n): a = 1这时我们再计算执行次数的话，就变成了：
。在这里，我们用他的计算次数来代表他的时间复杂度，计算次数越多，算法执行时间越长。
在时间复杂度的计算中，一般只保留最高次的项，并且不保留系数，那么这样简化以后，我们说这个代码的时间复杂度为 O(n^2)。 算法常数
细心的同学可能会思考一个问题，上面代码中，循环最里层只执行了一个 a = 1 的操作。如果再执行一个 a = 2 的操作呢？ Python3
def func(): for i in range(n): for j in range(i, n): a = 1 a = 2 重新计算代码的计算次数，可以看到我们的计算次数确实增加了一倍。
在本篇文章的最后，我们来回顾一些常见的时间复杂度。 常数时间复杂度
第一个例子，我们刚才说过，他的时间复杂度为 O(1)，也叫常数复杂度。 Python3
#常数复杂度def func(n): a = 1线性时间复杂度
第二个例子，我们有一重循环，所以复杂度为 O(n)，也叫作线性复杂度。 Python3
#线性复杂度def func(n): for i in range(n): a = 1多项式时间复杂度
第三个例子，我们有两重循环，时间复杂度为 O(n^2)，我们也可以继续累多层循环，这些都是多项式复杂度。 Python3
#多项式复杂度 1def func(n): for i in range(n): for j in range(n): a = 1
Python3
#多项式复杂度 2def func(n): for i in range(n): for j in range(i, n): a = 1指数时间复杂度
看一个复杂些的例子，这是一个递归函数，计算 n 需要先计算两遍 n-1，那等于说要计算 4 遍 n-2，8 遍 n-3...一直最后到 1。所以我们说这个函数的时间复杂度为 O(2^n)，这是一个指数复杂度的算法。大多数搜索算法的复杂度都是指数级别。 Python3
#指数复杂度def func(n): if n <= 1: return n return func(n-1) + func(n-1)对数时间复杂度
和指数复杂度对应的是对数复杂度，下面对于 n 每次我们询问 n/2，那么最终的函数调用次数大约为以 2 为底数的 log2(n)。 Python3
def func(n): if n <= 1: return n return func(n//2)渐进时间复杂度
接下来我们分析两个稍微复杂一点的例子。首先是下面这个函数： Python3
def func(n): if n <= 1: return mid = n // 2 for i in range(mid+1, n): a = 1 func(mid)
该函数的时间复杂度是？
A. O(n)
B. O(n^2)
C. O(2^n)
D. O(log(n)) 均摊时间复杂度
最后我们来看看均摊复杂度，这也是复杂度分析中较难的一种类型。
假设我们有一个全局数组 a，然后有一个函数 func，如果输入是 0，我们就往 a 里放一个数，如果输入不是 0，我们就把 a 中的数全部 pop 出来。这样经过 n 次操作以后，算法时间复杂度是多少？ Python3
a = []def func(x): if x == 0: a.push(x) else: while a.size() > 0: a.pop()for i in range(n): func(某个 x)我们首先来分析单次的时间复杂度：
显然对于 x = 0 的时候，我们只是放一个数到数组，单次操作时间复杂度为常数。如果有 n 次的话，时间复杂度是 O(n)。
麻烦的是 x 不等于 0 的情况，极端情况下，我们先放了 n - 1 个数，然后最后一次把这些数都 pop 出来，这样单次操作的时间复杂度就是 O(n) 了。假设有 n 次操作总体时间复杂度这么算是 O(n^2)。
但是第二种情况是不符合直觉的，因为显然我们不会每一次都 pop n 个数出来，第一次 pop 完了以后后面的 pop 都几乎没有代价了。
不妨换一个思路，第二个操作中，每次都会从数组中拿数出来，但是不管他每次操作具体拿出来多少，总共能拿出来的数的数量也就是我们插入到数组中的数的数量。而插入的数的总数最多为 n。因此所有的 pop 操作 加起来 的时间复杂度为 O(n)。因此，步骤一和步骤二的时间复杂度都是 O(n)，总体时间复杂度为 O(n)。
窥视卡
雷达卡
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜