本文主要介绍算法的时间复杂度和空间复杂度的相关知识。

1 概述

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

对于同一个问题，使用不同的算法，也许最终得到的结果是相同的，但在执行该算法所需的时间和（存储）资源可能会有很大的区别，那么我们应该如何去衡量不同算法之间的优劣呢？目前主要是从算法所占用的“时间”和“空间”两个维度去进行评价。

时间维度是指执行算法所消耗的时间，通常用“时间复杂度”来描述，空间维度是指执行算法需要占用的内存空间大小，通常用“空间复杂度”来描述。

2 时间复杂度

大O表示法是一种算法复杂度的“相对”“表示”方式，在这个句子中：

相对（relative）：我们只能比较相同的事物，不能把一个做算数乘法的算法和排序整数列表的算法进行比较，这是没有意义的；

表示（representation）：大O表示法把算法间的比较简化为了一个单一的变量，这个变量的选择基于观察或假设。例如，排序算法之间的比较通常是基于比较操作（比较2个结点来决定这2个结点的相对顺序）的，这里面就假设了节点间的比较操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式。

常见的时间复杂度量级如下：

• O(1)：常数阶

• O(n)：线性阶

• O(n^2)：平方阶

• O(logn)：对数阶

• O(nlogn)：线性对数阶

• O(2^n)：2的n次方阶

• O(n!)：阶乘阶

说明：在表示算法复杂度时，对数logn的底数为2。

这几种时间复杂度的优劣性如下图所示：

下面分别介绍几种常见的时间复杂度。

2.1 O(1)

对于O(1)常数阶时间复杂度，仅需固定次数（如1次、5次等等）即可完成算法的操作，而不会受其他因素影响，即其他因素不会参与到算法的操作中。

下面给出一个交换参数a和b位置的示例代码：

void swapTwoInts(int &a, int &b) {int temp = a;a = b;b = temp;
}

在上面的示例代码中，仅需一次操作即可完成变量交换算法（操作），而在此过程中，其他因素不会影响到该算法的时间复杂度。上述代码的运行过程示意图如下：

2.2 O(n)

对于O(n)线性阶时间复杂度，需要执行n次操作（如变量交换、加法等算法运算等）方可完成算法的完整操作。

下面给出一个求累加和的示例代码：

int sum (int n) {int ret = 0;for (int i = 0; i <= n; i++) {ret += i;}return ret;
}

在上面的示例代码中，for循环中的代码（加法运算）会被执行n次，即需要n次操作方可完成累加算法（操作），因此该算法的时间复杂度为O(n)。上述代码的运行过程示意图如下：

注意，c*O(n)表示的时间复杂度与O(n)相同。例如2*O(n)或(1/2)*O(n)均表示时间复杂度为O(n)。

2.3 O(n^2)

对于O(n^2)平方阶时间复杂度，需要执行(n^2)次操作（如变量交换、加法等算法运算等）才能完成算法的完整操作。

下面给出一个选择排序（selection sort）的示例代码：

void selectionSort(int arr[],int n) {for (int i = 0; i < n; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}swap(arr[i], arr[minIndex]);}
}

在上面的示例代码中，for循环中的代码中又嵌套了一层for循环（双重循环），即把O(n)的代码再嵌套循环一遍，因此该算法的时间复杂度就是O(n^2)了。上述代码的运行过程示意图如下：

这里推导一下该算法的执行过程：

• 当”i = 0“时，第二重循环需要运行(n – 1)次；

• 当”i = 1“时，第二重循环需要运行(n – 2)次；

依此类推，可以得到公式：

(n - 1) + (n - 2) + (n - 3) + ... + 0
= (0 + n - 1) * n / 2
= (n ^ 2 - n) / 2

因此，该算法的时间复杂度为O(n^2)。

当然，并非所有双重循环的时间复杂度都是O(n^2)，如果内层循环次数为常数c，则时间复杂度为c*O(n)=O(n)。示例代码如下：

void printInformation(int n) {for (int i = 1; i <= n ; i++) {for (int j = 1; j <= 30; j++) {cout << "Hello World!" << endl;}}
}

2.4 O(logn)

对于O(logn)对数阶时间复杂度，需要执行(logn)次操作（如变量交换、加法等算法运算等）才能完成算法的完整操作。

下面给出一个二分查找（binary search）的示例代码：

int binarySearch(int arr[], int n, int target) {int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;}if (arr[mid] > target) {right = mid - 1;}else {left = mid + 1;}}return -1;
}

在上面的示例代码中，通过while循环中的除2操作，将每次搜索范围缩小至前一次的一半，因此最坏的情况需要经过logn次操作跳出循环，因此该算法的时间复杂度为O(logn)。上述代码的运行过程示意图如下：

这里推导一下该算法的执行过程：

• 在第1次查找完成后，剩余的搜索范围为n*(1/2)；

• 在第2次查找完成后，剩余的搜索范围为n*(1/2)*(1/2)；

依此类推，可以得到公式：

n*((1/2)^k)=1
k=logn

说明：

• n为数组长度；

• k为最坏情况下查找到目标元素所需的次数（或者跳出循环的次数）；

• 等式“n*((1/2)^k)=1”中右侧的“1”表示剩余的待搜索范围。当剩余的搜索范围为“1”时，该次搜索操作完成后，无论是否找到了目标元素，此算法都将结束执行。

因此，该算法的时间复杂度为O(logn)。

2.5 O(nlogn)

将时间复杂度为O(logn)的代码循环n次，则该算法的时间复杂度为n*O(logn)，即O(nlogn)。

示例代码如下：

void hello() {for (i = 1; i < n; i++) {int j = 1;while (j < n) {j = j * 2;}}
}

3 其他几种时间复杂度

本章介绍以下几种复杂度：

• 递归算法(recursive algorithm)的时间复杂度；

• 最好情况(best case)时间复杂度；

• 最坏情况(worst case)时间复杂度；

• 平均情况(average case)时间复杂度；

• 均摊(amortized)时间复杂度。

3.1 递归算法时间复杂度

3.1.1 一次递归调用

如果递归函数中，只进行了一次递归调用，且递归深度为depth，同时递归函数中操作的时间复杂度为T，则该递归算法的总体时间复杂度为O(T * depth)。

下面给出一个使用递归函数的二分查找（binary search）的示例代码：

int binarySearch(int arr[], int left, int right, int target) {if (left > right) {return -1;}int mid = left + (right - left) / 2; if (arr[mid] == target) {return mid;  }else if (arr[mid] > target) {return binarySearch(arr, left, mid - 1, target);} else {return binarySearch(arr, mid + 1, right, target);}
}

在上述代码中，递归函数中每次只可进行一次递归调用（if-else判断条件），由于递归函数中的除2操作，使得递归深度为logn，同时递归函数中操作的时间复杂度为1（无循环等），因此该算法的时间复杂度为O(1 * logn) = O(logn)。

这里再给出一个使用递归函数计算累加和的代码示例：

int sum(int n) {if (n == 0) {return 0;}return n + sum(n - 1);
}

在上述代码中，递归深度随着n的增加而线性递增，即递归深度为n，同时递归函数中操作的时间复杂度为1（无循环等），因此该算法的时间复杂度为O(1 * n) = O(n)。该代码的运行过程示例图如下：

3.1.2 多次递归调用

递归算法中比较难计算的是多次递归调用的情况，在这种情况下，通常需要根据具体情况分析算法时间复杂度。

先看下面一段示例代码：

int f(int n) {if (n == 0) {return 1;}return f(n - 1) + f(n - 1);
}

在上述这段代码中，递归算法包含了2次递归调用，递归树中节点数就是代码操作的调用次数。假设n=3，则上述代码的运行过程示意图如下：

在上述示意图中，代码操作的调用次数计算公式如下：

1 + 2 + 4 + 8 = 15

从中可以寻找出如下规律：

2 ^ 0 + 2 ^ 1 + 2 ^ 2 + ... + 2 ^ n
= 2 ^ (n + 1) – 1
= 2 ^ n + 1

因此，该算法的时间复杂度为O(2^n)。

再看一个归并排序的代码示例：

void mergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{if(startIndex < endIndex){int midIndex = startIndex + (endIndex-startIndex) / 2;mergeSort(sourceArr, tempArr, startIndex, midIndex);mergeSort(sourceArr, tempArr, midIndex+1, endIndex);merge(sourceArr, tempArr, startIndex, midIndex, endIndex);}
}

在上述这段代码中，递归算法包含了2次递归调用。假设n=8，则上述代码的运行过程示意图如下：

通过观察上面的归并排序的递归树可知：

• 归并排序的递归树深度为logn；

• 归并排序的递归树中每个节点处理的数据规模是逐渐缩小的，但每一层的时间复杂度保持不变，为O(n)；

因此，归并排序的算法时间复杂度为O(nlogn)。

说明：归并排序算法时间复杂度的计算方式与3.1.1节“一次递归调用”中的计算方式类似。这里要强调的是，涉及到对此递归调用的时间复杂度计算时，需根据实际情况进行分析。

3.2 最好/最坏情况时间复杂度

最好或最坏情况下的时间复杂度指的是特殊情况下的时间复杂度。

现有如下示例代码（作用是查找某数值在数组中首次出现时的位置）：

int find(int array[], int n, int x) {for (int i = 0; i < n; i++) {if (array[i] == x) {return i;break;}}return -1;
}

上述代码的运行过程示意图如下：

通过上图可知，当数组中第一个元素就是要查找的数值时，时间复杂度就是O(1)；而当最后一个元素才是要找的数值时，时间复杂度则是O(n)。

简单总结一下，最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它所消耗的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它所消耗的时间是最长的。

3.3 平均情况时间复杂度

最好、最坏时间复杂度反应的是极端条件下的时间复杂度，通常发生的概率不大，不能代表平均水平。因此为了更好的表示一般情况下的算法时间复杂度，就需要引入平均情况时间复杂度。

平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示。

这里仍以3.2节中的find函数为例，从概率的角度看， 数值x在数组中每一个位置出现的可能性是相同的，都是1/n，同时对应位置的权重为n的实际值（如1、2、3...），因此，该算法的平均情况时间复杂度就可以用如下的方式计算：

(1/n)*1 + (1/n)*2 + (1/n)*3 + ... + (1/n)*n
= (n+1)/2

因此，find函数的平均时间复杂度为O(n)。

3.4 均摊时间复杂度

这里通过一个动态数组的push_back操作来理解均摊时间复杂度。示例代码如下：

template 
class MyVector {
private:T* data;// 存储数组中的元素个数int size;// 存储数组中可以容纳的最大的元素个数int capacity;// 复杂度为O(n)void resize(int newCapacity) {T *newData = new T[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}data = newData;capacity = newCapacity;}
public:MyVector() {data = new T[100];size = 0;capacity = 100;}// 平均复杂度为 O(1)void push_back(T e) {if (size == capacity) {resize(2 * capacity);}data[size++] = e;}// 平均复杂度为 O(1)T pop_back() {size --;return data[size];}
};

上述代码的运行过程示意图如下：

在上述代码中，push_back实现的功能是向数组的末尾增加一个元素。如果数组没有填满，则直接向其后面插入元素；如果数组已经填满了（即size == capacity），则将数组扩容一倍，然后再执行插入元素操作。

假设数组长度为n，则前n次调用push_back函数的时间复杂度都是O(1)级别，而在第(n+1)次则需要先进行n次元素转移操作，然后再进行1次元素插入操作，因此，第(n+1)操作的时间复杂度为O(n)。

所以，对于容量为n的动态数组，前面添加元素需要消耗了(1*n)的时间，同时扩容操作消耗n时间，总共消耗(2*n)的时间，因此，完整操作的均摊时间复杂度为：O(2n/n) = O(2)，也就是O(1)常数级别了。

通过以上内容，可以知道：一个相对比较耗时的操作（如本例中的扩容操作），如果能保证它不会每次都被触发，那么这个相对比较耗时的操作，它需要的时间是可以分摊到其它的操作中的。

4 空间复杂度

为了更好地介绍算法的空间复杂度，这里首先介绍一下程序的空间复杂度。

程序的空间复杂度是指运行完该程序所需内存的大小。

通过程序的空间复杂度，可以对运行该程序所需的内存量有个预先估计。一个程序执行时，除了需要存储本身所使用的指令、常数、变量和输入数据外，还需要存储一些操作数据的工作单元以及计算所需的信息。总体来说，程序执行时所需的存储空间包括以下两部分：

1. 固定空间：这部分存储空间的大小与输入/输出数据（的个数、数值）无关。这些空间主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间；

2. 可变空间：这部分存储空间主要包括动态分配的空间，以及递归栈的空间等。这部分的空间大小与就算法有关了。

算法的空间复杂度S(n)表示，其中n为问题的规模。空间复杂度可以理解为除了固定空间外，在算法运行过程中需要用到的、额外的存储空间。

5 时间复杂度与空间复杂度

对一个算法来说，其时间复杂度和空间复杂度往往是相互影响的。

例如，要判断某某年是不是闰年，有以下两种方法：

1. 可以编写一个算法来进行计算，每次给一个年份，然后通过计算得到该年份是否为闰年的结果；

2. 另一个方法是，先建立一个有5000个元素的数组（数组所包含的年数比现实多就行），然后把所有的年份设置为对应的数组下标，同时，如果是闰年，则该元素的值就设置为1，否则设置为0。这样一来，判断某一年是否是闰年，就变成了（通过索引）查找这个数组的某一元素的值是多少的问题了。此时，算法的计算次数被最小化了（时间复杂度最小），但是硬盘上或者内存中却需要存储这个长度为5000的数组内容了（空间复杂度最大）。

这就是个典型的“使用空间换时间”的例子了。

当追求一个较好的时间复杂度时，可能会使空间复杂度变差，即可能导致占用更多的存储空间；反之，追求一个较好的空间复杂度时，也可能会使时间复杂度变差，即可能导致更长的运行时间。

此外，还有一些因素也会影响到算法的性能，如算法的使用频率、算法处理的数据量的大小、算法描述语言的特性等等，

因此，在设计算法时，需要根据算法运行环境的实际情况（如CPU性能、内存大小等），对时间复杂度和空间复杂度进行取舍权衡，同时还需想到其他一些可能会影响到算法性能的因素（如海量数据处理场景、实现语言间的差异等），综合考虑这些因素之后，最终才能设计出一个比较好的算法。