算法复杂度包括时间复杂度和空间复杂度。好算法的评判标准就是高效率和低存储，高效率即时间复杂度小，低存储即空间复杂度小。

1. 如何计算一个算法的时间复杂度

时间复杂度指算法运行需要的时间。我们一般将算法的基本运算执行次数作为时间复杂度的度量标准。

总的执行次数为2× n +3。如果用一个函数 T ( n )表达： T ( n )=2 n +3，则当 n 足够大时，例如 n =10 ⁵ 时， T ( n )=2×10 ⁵ +3。算法运行时间主要取决于最高项，后面的可以忽略不计。因为如果你告诉朋友买车花了20万零199元，大家都认为是20万元，没有人关心后面的尾数。如果一个人是亿万富翁，那么不管其有2亿元还是10亿元，都是亿万富翁。因此在表达时舍小项、舍系数，只看最高项就可以了。如果用时间复杂度的渐进上界 O 表示，那么该算法的时间复杂度为 O ( n )。

其实完全没有必要计算每一行代码的运行次数，只需计算语句频度最多的语句即可。循环内层的语句往往是运行次数最多的，对运行时间贡献最大。例如，在下面的算法中，“total=total+i*j”是对算法贡献最大的语句，只计算该语句的运行次数即可。该算法的时间复杂度为 O ( n ² )。

并不是对每个算法都能直接计算运行次数。有些算法如排序、查找、插入等，可以按最好、最坏和平均情况分别求算法渐进复杂度。但在考察一个算法时，我们通常考察最坏的情况是怎样的，而不是考察最好的情况，最坏的情况对于衡量算法的好坏具有实际意义。

2. 如何计算一个算法的空间复杂度

空间复杂度指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：输入输出数据、算法本身、额外需要的辅助空间。

输入输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间，是衡量空间复杂度的关键因素。我们一般将算法的辅助空间作为衡量空间复杂度的标准。

例如，将两个数交换。

两个数的交换过程如下图所示。

上图中的步骤标号与swap函数中的语句标号一一对应，该算法使用了一个辅助空间temp，空间复杂度为 О (1)。

注意：在递归算法中，每一次递推都需要一个栈空间来保存调用记录，因此计算空间复杂度时需要计算递归栈的辅助空间。

例如，计算 n 的阶乘。

递推和回归在系统内部使用栈实现，栈空间的大小为递归树的深度。计算 n 的阶乘，其递归树如下图所示。

计算 n 的阶乘时，递归树的深度为 n ，因此计算 n 的阶乘的递归算法的空间复杂度为 О ( n )。

常见的算法时间复杂度如下。

（1）常数阶：算法运行的次数是一个常数，例如5、20、100，通常用 О (1)表示。

（2）对数阶：时间复杂度运行效率较高，常见的有 О (log n )、 О ( n log n )等。

（3）多项式阶：很多算法的时间复杂度是多项式，常见的有 О ( n )、 О ( n ² )、 О ( n ³ )等。

（4）指数阶：指数阶时间复杂度运行效率极差，是程序员避之不及的。常见的有 О (2 ⁿ )、 О ( n !)、 О ( n ⁿ )等。

常见的时间复杂度函数曲线如下图所示。

从上图可以看出，指数阶增量随着 x 的增加而急剧增加，而对数阶增加缓慢。它们之间的关系为 О (1)< О (log n )< О ( n )< О ( n log n ) < О ( n ² )< О ( n ³ )< О (2 ⁿ ) < О ( n !)< О ( n ⁿ )。

通过曲线可以大致看出时间复杂度在数量级上的差别，但仍然没有具体的形象。下面通过具体的时间来看看时间复杂度在数量级上的差别。

因为一天有24小时，每小时有60分钟，每分钟有60秒，所以：

● 一天 有24×60×60≈25×4000=10 ⁵ 秒；

● 一年 有365×10 ⁵ ≈3×10 ⁷ 秒；

● 100年 有100×3×10 ⁷ ≈3×10 ⁹ 秒；

● 三生三世 有3×3×10 ⁹ ≈10 ¹⁰ 秒。

如果有10亿数据排序，10亿=10 ⁹ ，那么两种不同机器运算的时间如下：

（1）普通PC：10 ⁹ 次运算/秒。

● 如果排序的时间复杂度为 O ( n ² )，则需要(10 ⁹ ) ² /10 ⁹ =10 ¹⁸ /10 ⁹ =10 ⁹ 秒≈30年。

● 如果排序的时间复杂度为 O ( n log n )，则需要(10 ⁹ ×log10 ⁹ )/10 ⁹ =(10 ⁹ ×30)/10 ⁹ =30秒。

（2）超级计算机：10 ¹⁷ 次运算/秒。

● 如果排序的时间复杂度为 O ( n ² )，则需要(10 ⁹ ) ² /10 ¹⁷ =10 ¹⁸ /10 ¹⁷ =10秒。

● 如果排序的时间复杂度为 O ( n log n )，则需要(10 ⁹ ×log10 ⁹ )/10 ¹⁷ =(10 ⁹ ×30)/10 ¹⁷ =3×10 ^-7 秒。

注意：2 ¹⁰ =1024≈10 ³ ，2 ³⁰ ≈10 ⁹ ，log10 ³ ≈log2 ¹⁰ ≈10，log10 ⁹ ≈log2 ³⁰ ≈30。 Q9Nx1VHT0S6ihJbZh/CX2FmQNMDgFBSygJelYHckFnTVM9A5FA8JnvUGUgfEFAnW