原因

关于代码的时间复杂度，我们可能在 大学里 的计算机基础、 数据结构、 算法导论 等一系列的课程中，学习或接触过。几乎所有计算机系 或 数学计算机系的 都对它们很熟悉，没一门语言都不会逃过时间复杂度，这个说起来算是非常基础的知识点了，那我为什么还要拿到进阶里面来说呢，因为日常中的 刚刚入门的 pythoner或者非科班出身的程序员 很少注意他们编写的程序时间复杂度，掌握好时间复杂度是掌握算法的很重要的因素，因为算法初衷就在于降低时间复杂度。

本篇使用 大O计数法来描述时间复杂度，引用维基百科的描述：

下面我会通过一些例子来举证它的时间复杂度：

线性搜索 （线性）

def linear_search(l, x):  # 线性搜索 列表的长度是决定性因素 O(len(l))
    for e in l:
        if e == x:
            return True
        return False

线性搜索的时间复杂度O(n)，取决于列表的长度，在时间复杂度上来说它是一种优秀复杂度，因为随着列表的增长，时间复杂度不会出现爆炸性的增长。

递归、单层循环（线性）

def fact(n):
    answer = 1  # 1
    while n > 1:  # 5 *n
        answer *= n
        n -= 1
    return answer  # 1   所有 5n + 2

看到上面的代码， answer赋值的时候进行了一步操作， 随后的while循环里，进行了5步操作，循环的时间复杂度取决于 n的大小，所以是5n， 最后return 又是一步操作，所以总的步数为5n+2，仔细算的是这样，但在大O表示法里，是忽略常数的（大O表示法通常会忽略常数,因为它关注的是算法的消耗时间随着N的变化而怎么变化，这样算有没有弊端呢，有的，就是某些情况下使用大O表示法的时间复杂度是一致的，但实际上是有差异的），所以如果用大O来表示的话，为O(n)。

def factor(n):  # 阶乘 O（n）  递归
    if n == 1:
        return 1
    else:
        return n * factor(n-1)

这段阶乘的代码，时间复杂度为O(n)

二分查找（对数-次线性）

def sqrt_bi(x, eps):  # 2分查找 30次
    low = 0.0
    high = max(1, x)
    ans = (high + low) / 2.0
    while abs(ans**2 - x) == eps:
        if ans**2 == x:
            low = ans
        else:
            high = ans
        ans = (high + low) / 2.0
    return ans 

上面这段代码，是用python实现的二分查找，它的的时间复杂度用大O表示法表述为为O(log(n))

def sqrt_exhaust(x, eps):
    step = eps ** 2  # 2
    ans = 0.0  # 1
    while abs(ans**2 - x) >= eps and ans <= max(x, 1):  # 8 * 循环运行的次数
        ans += step
    return ans  # 1 所有 3 + 8 * 循环运行次数

这两段代码的作用是相同的，但两种方法 输入100到最后求得结果0.0001 一个循环要花费 8000000 次 （第二种）一个只需要循环30次（第一种），当然这是算法的问题，只不过体现的是时间复杂度，当你掌握了时间复杂度后，你才会去考虑算法的优劣性。

多项式（平方）

def is_subset(l1, l2):   # 多项式 O(len(l1) * len(l2))
    for e1 in l1:
        matched = False
        for e2 in l2:
            if e1 == e2:
                matched = True
                break
        if not matched:
            return False
    return True

上面这段代码，算法运行时间会成二次方的增长，理论上来说，这是相当糟糕的时间复杂度了，但这样代码在新手里，是非常常见的，我本人初期就写过很多这样的代码。

汉诺塔（指数）

def get_subsets(l):    # 指数算法  汉诺塔 O(2^n)
    if len(l) == 0:
        return [[]]
    smaller = get_subsets(l[:-1])
    extra = l[-1:]
    new = []
    for small in smaller:
        new.append(small + extra)
    return smaller + new

在这段汉诺塔代码里，并不是平常见到的汉诺塔的写法，算法的运行时间会成2的n次方增长，实际上是糟糕的时间复杂度了。

在日常的生产活动中，我们应该竭力寻找时间复杂度小的算法，如 线性时间，掌握了时间复杂度有助于你写出或找到更好的算法，选择好的算法也是性能优化的一部分。