时间复杂度

要想知道一个算法执行所耗费的时间，最直接的办法是上机运行测试间，但是没必要每个算法都上机测试，再说使用同样的算法，在不同的机器上花费的时间也不同。为了更好地描述算法的运行地时间，引入了时间复杂度的概念。

概述

时间复杂度是评价算法流程的一个标准，它是一个算法流程中常数时间的操作数量指标。

时间复杂度常用O来表示（这个符号的意思是“忽略重要项以外的内容”，读音同Order），在常数操作数量的表达式中，不要低阶项，只要高阶项，并且不要高阶项的系数，剩下的部分如果记为f(N)，那么时间复杂度为O( f(N) )。（极限的思想）

时间复杂度该指标只与数据量有关，与过程之外的优化无关。当我们要处理的样本量非常大的时候，我们会发现底阶项、每一项的系数都不是最重要的了，正在重要的是高阶项是什么。

常数时间的操作

常数时间的操作是指：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作，例如：数组寻址、加减乘除操作、位运算操作等等，这些都是常数数间的操作，反之执行时间不固定的操作都不是常数时间的操作。

常见常数时间的操作

• 常见的算术运算（+、-、*、/、%等）
• 常见的位运算（>>、>>>、<<、｜、&、^等）
• 赋值、比较、自增、自减操作等

时间复杂度如何确定

如何确定算法流程的总操作数与样本量之间的表达式关系？

• 想象该算法流程锁处理的数据状态，按照最差的情况来
• 把整个流程彻底拆分成一个个基本动作，保证每个动作都是常数时间的操作
• 如果数据量为N，看看基本动作的数量和N是什么关系

选择排序的时间复杂度

我们知道选择排序的算法步骤（假设已经掌握了选择排序）：

步骤一：从数列中找最小值
步骤二：将最小值和数列最左边的数字进行交换，排序结束。回到步骤一。

假如数列中有n个数字，那么步骤一只需要确认n个数字即可，这里“找最小值”是个计算的基本单位（一个常数时间的操作），需要的时间我们设为Tc，那么步骤一的运行时间为 n·Tc 。接下来，步骤二中将两个数字进行交换，也是一个常数时间的操作，需要的时间我们设为Ts。那么步骤一二总共需要重复n次，每经过一轮的步骤，需要查找的数字就减少1个，总的运行时间表达式如下：

$\begin{aligned} f(x) &= (n\cdot T_{c} + T_{s}) + ((n-1)\cdot T_{c} + T_{s}) + ((n-2)\cdot T_{c} + T_{s}) + \cdot \cdot \cdot + (2\cdot T_{c} + T_{s}) + (1\cdot T_{c} + T_{s}) \\ &= \frac{1}{2} \cdot T_{c} \cdot n(n+1) + T_{s} \\ &= \frac{1}{2} \cdot T_{c} \cdot n^{2} + (\frac{1}{2} \cdot T_{c} + T_{s}) \cdot n \end{aligned}$

上面的公式只是一个常数操作数量的表达式，我们进一步简化结果得到时间复杂度。首先，Tc和Ts都是常数时间的操作，可以删掉。接下来从表达式可以看出，最直接影响算法时间的是n，只有它会根据输入的变化而变化。而随着n变得越来越大，对表达式影响最大的就是 n^2，所以删掉其他部分我们有：

$\frac{1}{2} \cdot T_{c} \cdot n^{2} + (\frac{1}{2} \cdot T_{c} + T_{s}) \cdot n = O(n^{2})$

所以选择排序的时间复杂度是 O(n^2) ， 算法运行时间最长也就是 n^2 的常数倍。

再回顾示例的算法时间复杂度的计算：是不是对常数操作量表达式进行了 删除低阶项，保留高阶项且不要高阶项目的系数，剩下的部分表达式可以记为 f(n) = n^2, 时间复杂度就为 O(n^2)

其实 时间复杂度 简单理解为 用数学方式 来表示输入数据的量(n)和运行时间的关系。

时间复杂度如何对比

我们知道，解决一个问题可以有多种算法，在知道各个算法的时间复杂度情况下，如何比较？通常情况下先看算法的流程指标，也就是时间复杂度，在指标相同的情况下，再比较系数大小。

例如：一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数组长度为N，B数组长度为M。对这个问题有三种算法：

算法流程1：对于数组B中的每一个数，都在A中通过遍历的方式找一下；  
时间复杂度：O(M * N)

算法流程2：对于数组B中的每一个数，都在A中通过二分的方式找一下；  
时间复杂度：O(M * logN)

算法流程3：先把数组B排序，然后用类似外排的方式打印所有在A中出现的数； 
时间复杂度：O(M * logM ) + O(N + M)

显然方法1的时间复杂度是最差的，对于方法二、三需要确定具体的样本量才能分析优劣。对于数组A的长度较小的时候（N更小），方法二更好，因为logN更小；相反而言，对于数组B的长度较小的情况下，方法三更好。