一、前言

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二就是分析算法的时间复杂度和空间复杂度。

针对同一问题，可以有很多种算法来解决，但不同的算法在效率和占用存储空间上的区别可能会很大。那么，通过什么指标来衡量算法的优劣呢？其中，效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。

时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。

在实践中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。

一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况。最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现得比较频繁，也意味着平均情况和最坏情况一样差。

通常，时间复杂度要比空间复杂度更容易出问题，更多研究的是时间复杂度，实践中，如果没有特殊说明，讲的也是时间复杂度。

二、何为时间复杂度？1、时间复杂度的含义

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

2、时间复杂度的分级

我们可以按复杂度是否为多项式进行时间复杂度分级：

一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的时间复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的时间复杂度，其复杂度计算机往往不能承受。

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

一般情况下有：非多项式时间 > 多项式时间 > 线性时间 > 常数时间。但是一定要注意这些大于并不是对于所有n的情况成立的，只是在说随着n增加前者一定会超过后者。关于多项式时间的概念，见附录2。

三、时间复杂度分析

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

事后统计的方法

这种方法可行，但不是一个好的方法。该方法有两个缺陷：

要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。事前分析估算的方法

因事后统计方法更多地依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。

在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

算法采用的策略、方法；编译产生的代码质量；问题的输入规模；机器执行指令的速度。3.1 时间复杂度

要获得算法的时间复杂度，最直观的想法是把算法程序运行一遍，自然可以获得。但实践中往往受限于测试环境、数据规模等因素，直接测试算法要么难以实现，要么误差较大，而且理论上也没必要对每个算法都进行一遍测试，只需要找到一种评估指标，获得算法执行所消耗时间的基本趋势即可。

3.2 时间频度

通常，一个算法所花费的时间与代码语句执行的次数成正比，算法执行语句越多，消耗的时间也就越多。我们把一个算法中的语句执行次数称为时间频度，记作 T(n)。

3.3 渐进时间复杂度

在时间频度T(n)中，n代表着问题的规模，当n不断变化时，T(n)也会不断地随之变化。那么，如果我们想知道T(n)随着n变化时会呈现出什么样的规律，那么就需要引入时间复杂度的概念。

一般情况下，算法基本操作的重复执行次数为问题规模n的某个函数，也就是用时间频度 T(n) 表示。如果存在某个函数 f(n)，使得当 n 趋于无穷大时，T(n)/f(n) 的极限值是不为零的常数，那么 f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。

渐进时间复杂度用大写O表示，所以也称作大O表示法。算法的时间复杂度函数为：

T(n) = O(f(n))

T(n)=O(f(n))表示存在一个常数C，使得在当n趋于正无穷时总有T(n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。

常见的时间复杂度有：

表-1

图-1

图-1为不同类型的函数的增长趋势图，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

常见的算法时间复杂度由小到大依次为：

值得留意的是，算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围，在一定问题规范范围之前某一算法比另外一算法高效，而过了一个阈值之后，情况可能就相反了，通过图-1我们可以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能与上面算法的排序相反的原因。

3.4 如何推导时间复杂度

上面我们了解了时间复杂度的基本概念及表达式，那么实践中我们怎么样才能通过代码获得对应的表达式呢？这就涉及到求解算法复杂度。

求解算法复杂度一般分以下几个步骤：

找出算法中的基本语句

算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。

计算基本语句的执行次数的数量级

只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。

用大Ο表示算法的时间性能

将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则：

用常数1取代运行时间中的所有加法常数；只保留时间函数中的最高阶项；如果最高阶项存在，则省去最高阶项前面的系数。

下面通过具体的实例来说明以上的推断步骤和规则。

3.5 时间复杂度实例常数阶 O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)，如：

int i = 1;int j = 2;int k = 1 + 2;

上述代码执行时，单个语句的频度均为 1，不会随着问题规模 n 的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。

对数阶 O(log n)

先来看对应的示例代码：

int i = 1; // ①while (i <= n) {i = i * 2; // ②}

在上述代码中，语句①的频度为1，可以忽略不计。

语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是 1*2*2*2...*2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。

其实上面代码的时间复杂度公式如果精确地来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。

线性阶 O(n)

示例代码：

int j = 0; // ①for (int i = 1; i < n; i++) { // ②    j = i; // ③    j++; // ④}

上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1) 来表示。进而可以推到 T(n)=1+n+(n-1)+(n-1)=3n-1，即 O(n)=3n-1，去掉低次幂和系数即 O(n)=n，因此 T(n)=O(n)。

在上述代码中for循环中的代码会执行n-1遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。

线性对数阶 O(nlogN)

示例代码：

for (int m = 1; m < n; m++) {    int i = 1; // ①    while (i <= n) {        i = i * 2; // ②    }}

线性对数阶要对照对数阶 O(log n) 来进行理解。上述代码中for循环内部的代码便是上面讲到的对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是 n*O(log n) 了，于是记作 O(nlog n)。

平方阶 O(n²)

示例代码：

int k = 0;for (int i = 0; i < n; i++) {    for (int j = 0; j < n; j++) {        k++;    }}

平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即 O(n2)。

如果将外层循环中的n改为 m，即：

int k = 0;for (int i = 0; i < m; i++) {    for (int j = 0; j < n; j++) {        k++;    }}

那么，对应的时间复杂度便为：O(m * n)。

同理，立方阶 O(n³)、K 次方阶 O(n^k)，只不过是嵌套了3层循环、k层循环而已。

排序算法对比

上面介绍了各种示例算法的时间复杂度推理过程，对照上面的时间复杂度以及算法效率的大小，来看一下我们常见的针对排序的几种算法的时间复杂度对比。如图-2所示。

图-2

四、空间复杂度分析

空间复杂度主要指执行算法所需内存的大小，用于对程序运行过程中所需要的临时存储空间的度量，这里的空间复杂度同样是预估的。

程序执行除了需要存储空间、指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括：指令空间（即代码空间）、数据空间（常量、简单变量）等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。

一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。

下面看两个常见的空间复杂度示例：空间复杂度O(1)和O(n)。

空间复杂度 O(1)

空间复杂度为O(1)的情况的示例代码与时间复杂度为O(1)的实例代码一致：

int i = 1;int j = 2;int k = 1 + 2;

上述代码中临时空间并不会随n的变化而变化，因此空间复杂度为O(1)。总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为O(1)，即S(n) = O(1)。

空间复杂度 O(n)

示例代码：

int j = 0;int[] m = new int[n];for (int i = 1; i <= n; ++i) {    j = i;    j++;}

上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。

五、附录附录1 符号表示

时间复杂度T(n)=O(f(n))，该公式中的O符号，即Landau符号，其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。

附录2 P问题与NP问题

设多项式f(n)的形式为：

多项式时间可以定义为：存在一个多项式，使得对任意的输入n，A 的计算次数 C(n;A)≤f(n) 。

只要问题的计算时间相对于问题大小n可以表示为这样的形式，这个问题就属于多项式时间问题。我们在考虑计算复杂度时，只关注它的最高次项 而将其他低次项以及各项前的系数都忽略掉，记为O(n^k)。我们将所有此类问题都归为一个大类，P问题。

为什么这个多项式时间那么重要而且经常提到？因为它是当今计算科学里，它是问题“可解”与“不可解”的分水岭。理论上，只要此问题属于P之一大类，目前的计算机都能在可接受的时间内找到问题的最优解；实际上，当指数系数k很大时最优解的寻找也会很困难，但无论如何理论上是可行的。反之，如果计算时间不能表述为这样的形式，我们就将其归为NP问题（非多项式时间）。注意我这里说的“不可解”不是说问题完全无法求解，实际上大部分NP问题，要找到可行解相当容易，但是最优解却几乎无法在可接受的时间内找到。