02-为什么这个算法要执行这么长时间？

1. 什么是时间复杂度

你好，我是悦创。

一个高级语言编写的程序的运行时间主要取决于三个因素：

• 算法的方法，策略；
• 问题的输入规模；
• 计算机执行指令的速度。

问题的输入规模是客观的、限定的，要加快算法的效率绝不能影响问题的输入规模。计算机执行指令的速度虽然可以有显著提升，但其发展时间较长，也不是确定的，总不能终日盼着计算机性能的提升。所以提高算法的效率，减少程序运行时间，改进算法的策略是至关重要的。

在讲解时间复杂度之前，需先引入一个概念，时间频度。时间频度代表一个算法中的语句执行次数，其又可以被称为语句频度。显然，时间频度越高的算法运行的时间越长。时间频度也可被记为 $T(n)$，其中 n 为问题的规模，即输入值的规模。

在讲解时间复杂度之前，我们需要理解一个基础概念：算法中语句的执行次数。执行次数是指在算法执行过程中，某些特定语句的执行频次。显然，一个算法中的语句执行次数越多，其运行的时间可能会越长。为了便于分析，我们可以把这个执行次数记作 $T(n)$，其中 $n$ 代表了问题的规模，即输入的大小。但需要注意的是，$T(n)$ 并非直接等于实际运行时间，而是反映了算法运行时间随问题规模变化的趋势，即时间复杂度

时间复杂度的具体定义为：若有某个辅助函数 $f(n)$，使得的 $\frac{T(n)}{f(n)}$ 极限值（当 n 趋近于无穷大时)为不等于零的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作：$T(n)=O(f(n))$

称 $O(f(n))$ 为算法的渐进时间复杂度，简称时间复杂度。在数学上，大 O 符号用来描述一个函数数量级的渐近上界。

以上是纯数学分析，看不太懂的读者可以理解为时间复杂度就是算法运行时间和输入规模的关系。

2. 时间复杂度是渐进的

如果我们将算法中的一次计算记为 1，那么如果有 n 个输入值，算法对每一个输入值做一次运算，那么整个算法的运算量即为 n。这个时候，我们就可以说，这是一个时间复杂度为 $O(n)$ 的算法。

同理，如果仍有 n 个输入值，但算法对每一个输入值做一次运算这个操作需要再重复 n 次，那么整个算法的运算量即为 $n∗n=n^2$，时间复杂度为 $O(n^2)$ 。这时如果对每一个输入值做一次运算这个操作需要重复 $n+1$ 次，算法运算量变为：$n*(n+1)=n^2+n$

这时的时间复杂度是否改变为 $O(n^2+n)$ ？上文曾提到时间复杂度考察的是当输入量趋于无穷时的情况，所以当 n 趋于无穷的时候，$n^2$ 对算法运行时间占主导地位，而 n 在 $n^2$ 面前就无足轻重，不计入时间复杂度中。

换句话说，因为 $n^2+n$ 渐近地（在取极限时）与 $n^2$ 相等。此外，就运行时间来说，n 前面的常数因子远没有输入规模 $n$ 的依赖性重要，所以是可以被忽略的，也就是说 $O(n^2)$ 和 是 $O\frac{n^2}{2}$ 相同时间复杂度的，都为 $O(n^2)$。

3. 时间复杂度分析

让我们先看一段代码：

def square(n):
    Partial_Sum = 0
    for i in range(1, n + 1):
        Partial_Sum += i * i
    return Partial_Sum

代码的第二行只占一次运算，第三行的 for 循环中 i 从 1 加到了 n，其中过程包括 i 的初始化， i 的累加，和 i 的范围判断，分别消耗 1 次运算，n 次运算，和 n+1 次运算。

至此，代码的前三行共进行了 2n+3 次运算。第四行是相乘，相加，和赋值三个功能的组合的代码，相乘所需 n 次运算，相加所需 n 次运算，而赋值也需 n 次运算。所以第四行一共进行了 3xn 次运算。最后一行返回消耗一次运算。

总体来看，这段代码一共需进行 2n+3+3n+1=5n+4 次运算。根据上文的渐进原则，这段代码的时间复杂度为 $O(n)$。

通过上面的分析，可以看出细致的时间复杂度分析十分繁琐。但毕竟时间复杂度追求渐进原则，所以在这里为大家整理了一下快速算时间复杂度的技巧：

3.1 循环结构

for i in range(1, k*n+m+1):
    i += 1

上示代码中的 n 为输入规模，k，m 均为已知常数。因此根据渐进原则，只要 for 循环的循环范围是在 n 的有限倍数以内（range 的上界始终可以被表示为 k*m+n 的形式），则一个 for 循环的时间复杂度必然为 $O(n)$。

for i in range(n):
    for j in range(n):
        Partial_Sum += 1

我们将两个 for 循环迭代在一起。有 n 个不同的 i，每个 i 会对应 n 的不同的 j 的情况下，会有 $n*n=n^2$ 次第三行的操作。在这里我们可以说这段代码的时间复杂度为 $O(n^2)$。实际上，真实的运算次数会有 $k*n^2$ 次（k 为一个常数），其中 k 始终是有限的尽管 k 有时会非常大。

综上所述，我们可以总结出循环结构时间复杂度的一些规律：

• 无论是 for 还是 while 循环，只要循环的范围可以表示为 $k*n+m$，则该循环的时间复杂度为 $O(n)$；
• 如果循环中嵌套循环，则时间复杂度将便成每一层循环的时间复杂度相乘的结果；
• 在决定时间复杂度时，往往只需要关注层数最多 for 循环结构的时间复杂度，因为其它循环的时间复杂度很大可能上会被忽略。

3.2 递归结构

def feb(n):
    if n <= 1:
        return 1
    else:
        return feb(n - 1) + feb(n - 2)

如上所示的是一个计算斐波那契数列函数。而我们都是道斐波那契数列的公式为：

假设当输入规模为时该函数的运行次数为 $T(n)$，通过上示公式我们可以得到：

由于常数不会影响到函数整体的时间复杂度，所以可以被简化为：

到这一步，我们已经知道当输入规模为 n 时，斐波那契数列函数时间复杂度的递推公式，而我们只需求出通项公式即可分析出其时间复杂度为 $\large O((\frac{1 + \sqrt{5}}{2})^n)$，约为 $O(1.618^{n})$，简化默认为指数级复杂度 $O(2^{n})$ 。可以看出，该斐波那契数列函数的时间复杂度成指数增长，说明这是较为低效的一个递归函数。

4. 小结

在了解算法本质的同时，要掌握时间复杂度来判断一个算法的效率和实用性。相同问题时，算法的复杂度越低，证明算法的效率越高。本质上，输入规模往往是对空间复杂度与时间复杂度影响最大的因素。对于时间复杂度来说，输入量越多，所需处理的数据量越多，计算次数越多，算法运行的时间越多。

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】