数据结构修炼——时间复杂度？空间复杂度？教你如何衡量算法的优劣！！
目录
- 一、关于复杂度
- 二、时间复杂度
- 1 概念
- 2 大O的渐进表示法
- 3 练习
- 3.1 练习1
- 3.2 练习2
- 3.3 练习3
- 3.4 练习4
- 3.5 练习5
- 3.6 练习6
- 三、空间复杂度
- 1 概念
- 2 练习
- 2.1 练习1
- 2.2 练习2
- 2.3 练习3
- 2.4 练习4
- 小结
一、关于复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法运行的快慢程度，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度，所以我们如今已经不需要再特别关注一个算法的空间复杂度。尽管如此，我们还是要清楚地知道空间复杂度到底是怎么一回事，以及复杂度的一些概念。复杂度在往后的编程中会经常出现，更重要的是它还直接帮助了程序员衡量一个算法的优劣。
二、时间复杂度
1 概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度类似一个数学意义上的函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能精确计算的，只有实际将程序放在机器上跑起来才能知道。但是这并不实际，毕竟同一台电脑在不同状况下运行同一个程序速度都未必一样，遑论是不同性能的电脑。所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比。因此定义时间复杂度等于算法中基本操作语句的执行次数。即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
// 请计算一下 Func1 中 ++count 语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;//嵌套循环，有 N*N 次循环即执行了 N*N 次 ++count
}
}
for (int k = 0; k < 2 * N; ++k)
{
++count;//执行 2*N 次
}
int M = 10;
while (M--)
{
++count;//执行 10 次
}
printf("%d\n", count);
}
基本操作的执行次数：F(N) = N2 + 2N + 10
- N = 10，F(10) = 130
- N = 100，F(100) = 10210
- N = 1000，F(1000) = 1002010
百万次操作与一百多次操作看上去差距很大，但实际上电脑CPU的运算是很快的，基本都能超过亿这个级别，精确的操作次数并没有太大意义，所以相较而言它们并没有什么区别。时间复杂度实质上是从数量级的角度来评估一个算法，我们通常使用的评估复杂度的方法叫作：大O的渐进表示法。
2 大O的渐进表示法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导出执行次数的函数后，大多情况下我们只需要通过3个规则就能用大O正确地表示复杂度。
规则：
- 用1取代常数级的基本操作。（例如：F(N) = 1000000 时，时间复杂度用大O表示为O(1) ）
- 只保留最高阶项。（例如：F(N) = N2 + 2N + 10，时间复杂度为O(N2) ）
- 如果函数的最高次项系数为常数且不为1，可略去并置为1。（例如：F(N) = 100N2 + 2N + 10，时间复杂度仍为O(N2) ）
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数的数量级。
复杂度大致有以下数量级：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
我们可以按这个大小关系来保留高阶项，也可以通过这个大小关系来评估不同复杂度的大小。
其中常数阶O(1)，线性阶O(n)，平方阶O(n2)是最常见的，对数阶O(logn)与O(nlogn)使用情况稍特殊一些但在二分查找等算法中也常常出现，至于立方阶O(n3)开始时间复杂度就过高了，算法效率不高，用得更少了。
注：对数阶O(logn)与O(nlogn)中的底数是省略掉的，但大多为2，也存在直接写作O(lgn)与O(nlgn)的情况，遇到时注意不要与数学中的常用对数lg搞混，数学中lg是以10为底的对数
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N的数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般关注的是算法的最坏运行情况，所以我们取最坏情况的时间复杂度，即O(N)。
3 练习
3.1 练习1
// 计算 Func2 的时间复杂度？
void Func2(int N)
{
int count = 0;//有限次，常数次的赋值、打印等操作可以忽略
for (int k = 0; k < 2 * N; ++k)
{
++count;//执行次数为 2N
}
int M = 10;
while (M--)
{
++count;//执行次数为 10
}
printf("%d\n", count);
}
基本操作执行次数函数：F(N) = 2N + 10
首先判断出该函数不是常函数，于是取最高次项为F(N) = 2N，最高次项前系数可略去并置为1，所以时间复杂度为O(N)。
3.2 练习2
// 计算 Func3 的时间复杂度？
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < 2M; ++ k)
{
++count;//执行次数为 2M
}
for (int k = 0; k < 3N ; ++ k)
{
++count;//执行次数为 3N
}
int M = 10;
while (M--)
{
++count;//执行次数为 10
}
printf("%d\n", count);
}
基本操作执行次数函数：F(N) = 2M + 3N + 10
容易知道，该函数即不是常函数，也没有最高次项，像这种情况我们可以选择略去系数与常数，将时间复杂度表示为O(M+N)。当然，M与N实际上都是一次项，数量级其实是相同的，所以我们也可以直接将M看作N，变成O(2N)，同时略去系数，最终时间复杂度表示为O(N)。
3.3 练习3
// 计算 Func4 的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;//执行次数 100
}
printf("%d\n", count);
}
基本操作执行次数函数：F(N) = 100
常函数直接取1，时间复杂度为O(1)。
3.4 练习4
// 计算 BubbleSort 的时间复杂度？
void BubbleSort(int* arr, int n)
{
assert(arr);//对指针 arr 进行判空
for (int i = 0; i < n - 1; i++)
{
int exchange = 0;//一趟排序后，若未发生交换则判断数组有序
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j+1])
{
swap(a[j], a[j+1]);//交换 a[j],a[j+1]
exchange = 1;
}
}
if (exchange == 0) break;//数组有序，跳出循环结束排序
}
}
上面是一个简单的冒泡排序（从小到大排序），对于数组arr，长度为n，它的冒泡排序算法时间复杂度为多少呢？
首先我们要知道，时间复杂度针对的是算法的最坏运行情况，所以我们直接分析确认最坏情况即可。
从小到大排序的最坏情况就是数组序列是从大到小的顺序，这种情况下需要进行最多的交换操作。所以可以假设arr数组的序列为9 8 7 6 5 4 3 2 1 0，对它进行排序时，从i = 0到i = 8共计9趟排序，从第一趟到第九趟依次执行9、8…3、2、1次交换操作，每一趟的操作次数相加共计45次操作。容易知道，当数组长度为n时，需要n-1趟，且依次为n-1、n-2…3、2、1次交换操作，总计为n * (n - 1) / 2次基本操作。
所以基本操作次数函数为：F(N) = n * (n - 1) / 2 = n2 / 2 - n / 2
取最高次项并略去系数，则该冒泡排序的时间复杂度为O(n2)。
3.5 练习5
// 计算 fun 的时间复杂度？
void fun(int n)
{
int i = 1;
while (i <= n)
i = i * 2;
}
令循环次数为x，则有i * 2x > n，可化简为x > log2n，容易知道该函数的循环次数为大于log2n且离log2n最近的一个整数，而每一次循环只进行一次基本操作，所以循环次数等于基本操作次数，则时间复杂度为O(logn)。
3.6 练习6
// 计算斐波那契递归 Fib 的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
斐波那契数列，又称兔子数列：1，1，2，3，5，8…。即后一个数等于前两个数之和的数列，递推公式为：F(n) = F(n-1) + F(n-2) (n ≥ 2，n ∈ N+ ）。
递归大致情况如下：
Fib函数内部基本操作的次数可以看作1，即当N >= 3或N < 3时执行的return语句，因此基本操作执行次数直接等于Fib函数的调用次数。
如何知道Fib函数的调用次数呢？通过上图我们可以知道，F(N)大致是如同细胞分裂一样呈二倍增加的趋势的，当接近一个峰值后又开始稍缓趋势，达到后就开始迅速递减。最终结构大致为下图所示的三角结构（阴影部分）。
我们可以大致计算一下逐行递增部分的各行调用次数之和。
通过等比数列的求和公式可以得出Sn = 2x - 1。从上往下看，最左边的一行是逐行递减1的，所以一定存在x = N / C （x ∈ Z+ 且 x <= N，C为常数），由于递减的趋势远大于递增的趋势，所以将递减部分忽略后，我们可以得出递归次数的数量级大致在2n，则该递归函数Fib的时间复杂度为O(2n)。
三、空间复杂度
1 概念
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用的存储空间大小的量度 。
空间复杂度不是程序占用了多少字节的空间，这不仅难以计算更没有必要。空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
注：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时额外申请的空间来确定。
2 练习
2.1 练习1
问题：如果一个函数的内部中只定义了一个二维数组a[3][6]，请问这个函数的空间复杂度为多少？
这题我们可以轻易的知道该函数申请的变量个数一定为常数，所以可以直接得出其空间复杂度为O(1)。
2.2 练习2
// 计算 BubbleSort 的空间复杂度？
void BubbleSort(int* arr, int n)
{
assert(arr);
for (int i = 0; i < n - 1; i++)
{
int exchange = 0;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j+1])
{
swap(a[j], a[j+1]);
exchange = 1;
}
}
if (exchange == 0) break;
}
}
简单分析一下我们可以知道，int *arr与int n虽然是创建在栈上的两个临时变量，但这两个变量并不属于因为算法需要而临时占用的空间，而是算法外部传递过来的，所以不算入空间复杂度之内。真正属于算法临时占用空间的是变量int i，int j与int exchange所占用的空间，因此变量个数为3，根据大O的渐进表示法可知，空间复杂度为O(1)。
注：不要将多次循环中反复占用空间的同一变量相加，只需要关注相异的变量个数。
2.3 练习3
// 计算阶乘递归 Fac 的空间复杂度？
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N-1) * N;
}
虽然Fac函数中并没有创建临时变量，但我们知道递归调用是需要额外申请栈帧的，而该递归从F(N-1)到F(0)额外开辟了N个栈帧，每个栈帧使用了常数个空间，所以空间复杂度为O(N)。
2.4 练习4
// 计算函数 fun 的空间复杂度？
int** fun(int n)
{
int **s = (int **)malloc(n * sizeof(int *));
while(n--)
s[n] = (int *)malloc(n * sizeof(int));
return s;
}
该函数创建了一个二级指针int **s，申请了n个一级指针int *，并使二级指针int **s指向这n个一级指针所在的连续空间。接着在while的每次循环中依次申请了从n到1个int变量的空间，详细如下图所示。
了解数组的同学一定一下子就看出来了，这其实就是用二级指针模拟二维数组的创建，这实际上就是创建了一个n行，但依次从n列到1列的二维数组，因此该数组有n * (n + 1) / 2个元素，则空间复杂度为O(n2)。
小结
复杂度不仅在校招、面试以及OJ题中常有考察，也帮助了程序员更好的判断算法的优劣。复杂度分为时间复杂度与空间复杂度，而它们的表达都采用的是大O的渐进表示法。大O的渐进表示法是在数量级的层次上来估计算法的复杂度，常见的数量级与大小关系为：O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)。在这篇文章中，也给出了许多练习来帮助大家更好地理解复杂度的概念与掌握其运用方法。