如何衡量算法的效率？时间复杂度空间复杂度

本篇博客会讲解如何衡量一个算法的效率。衡量算法的效率，主要有2个维度，分别是：时间复杂度和空间复杂度。

1. 时间复杂度用来衡量算法的时间效率。时间复杂度越低，算法的耗时越短，效率则越高。
2. 空间复杂度用来衡量算法的空间效率。空间复杂度越低，算法占用的空间越小，效率则越高。

我们实现算法时，应该尽可能的降低算法的时间复杂度和空间复杂度，提升程序的效率。那么，如何计算时间复杂度和空间复杂度呢？

时间复杂度

时间复杂度计算的是算法执行的大致次数。举个例子：

void test(int n)
{int count = 0;for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){++count;}}for (int i = 0; i < 2*n; ++i){++count;}for (int i = 0; i < 10; ++i){++count;}
}

在函数test中，一共执行了几次++count呢？应该是n^2 + 2*n + 10次，这里为了直观，^并不表示异或的意思，而是次方的意思，比如n^2表示n的平方。

由于n^2 + 2*n + 10是一个准确的执行次数，我们称之为准确的时间复杂度函数式。一般来说，我们不会去考虑准确的时间复杂度函数式，有2个原因：

1. 不好计算。虽然看起来我们算出了“准确”的执行次数，但是其实也不是很准确，因为还有其他的语句执行没有计算进去，比如++i，变量count的定义等。哪怕把这些语句都计算进去了，也只是C语言语句的执行次数，在编译期间，会转换为汇编语言，这些指令的执行次数你算了吗？很难吧。
2. 不好比较。这些“准确”的式子太长了，如果有2个算法，想要比较它们的时间复杂度谁高谁低，不方便比较。

所以，时间复杂度一般采用大O的渐进表示法，这是一个估算值，规则是：

1. 如果只有常数项，用O(1)表示。
2. 只保留最高阶项。
3. 系数取1。
4. 一般变量取大写的N。

比如：准确的执行次数是n^2 + 2*n + 10，只取最高阶项N^2，且系数是1，得O(N^2)。下面再举几个例子：

• 准确的执行次数：3*n^3 + 2*n^2 + n + 10000，大O的渐进表示法：O(N^3)。
• 准确的执行次数：10000，大O的渐进表示法：O(1)。

下面再看一个问题：二分查找的时间复杂度是多少？不知道二分查找的朋友，戳这里

这里介绍时间复杂度的另外一个规则：只考虑最坏情况。那么，二分查找的最坏情况是什么呢？那就是：找不到！假设查找了x次，有2^x==N，即x=log₂N，所以时间复杂度是：O(log₂N)，一般来说底数的2会比较难打出来，我是用数学公式的方式打出来的，为了简单起见，就写O(logN)来代替。

空间复杂度

空间复杂度计算的是算法消耗的额外空间，计算方式和时间复杂度类似，一般采用大O的渐进表示法，表示算法创建的额外变量的大概个数。比如冒泡排序：

void bubble_sort(int arr[], int sz)
{for (int i=0; i<sz-1; ++i){bool flag = true; // 假设已经有序for (int j=0; j<sz-1-i; ++j){if (arr[j] > arr[j+1]){flag = false;int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}if (flag){break;}}
}

创建的额外变量有flag, i, j, tmp等，由于是常数项，故空间复杂度为O(1)。

举一个空间复杂度是O(N)的例子。对于递归求n的阶乘的算法：

int fac(int n)
{if (n <= 1)return 1;elsereturn n * fac(n-1);
}

由于会递归调用n次，每次调用都会创建一块栈帧，而栈帧里的额外变量是常数个，故空间复杂度是O(N)。

总结

1. 时间复杂度和空间复杂度衡量的是算法的时间和空间效率，一般更加看重时间效率，所以会有“以空间换时间”的做法。
2. 一般都采用大O的渐进表示法，时间复杂度计算大致的执行次数，空间复杂度计算额外创建变量的大致个数，计算时都只考虑最坏情况。
3. 只保留最高阶项，且系数取1。如果只有常数项，则复杂度为O(1)。

感谢大家的阅读！