【数据结构】算法的时间和空间复杂度

1.算法效率

我们平常编写程序解决问题时总会用到各种各样的算法（算法可以简单到只有几条代码，也可以复杂到让人捉摸不到头脑），而面对同一个问题时往往又会有不同的解决思路和算法，这时如何快速对算法效率进行有效判断变得异常重要。我们衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。虽然空间复杂度已不再是我们关注的重点，但我们还是要掌握它的计算方法。

2.时间复杂度

2.1时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。（找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。）

2.2时间复杂度的算法

我们先通过一个非递归函数的代码来计算它的时间复杂度（关于问题规模N的函数）。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
	{
 		for (int j = 0; j < N ; ++ j)
		{
			 ++count;
 		}
	 }
 
	for (int k = 0; k < 2 * N ; ++ k)	
 	{
		 ++count;
	}
	int M = 10;
	while (M--)
	{
	 ++count;
    } 
    printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

计算一下上面Func1中++count语句总共执行了多少次？
我们先将涉及到++count这条代码的部分分开来看：
第一部分是下面的两个for循环的嵌套使用，++count被执行N^2次。

for (int i = 0; i < N ; ++ i)
	{
 		for (int j = 0; j < N ; ++ j)
		{
			 ++count;
 		}
	 }
1
2
3
4
5
6
7

第二部分是下面单独一个for循环的使用，++count被执行2*N次。

for (int k = 0; k < 2 * N ; ++ k)	
 	{
		 ++count;
	}
1
2
3
4

第三部分是下面while()循环的使用，++count被执行了M次（也就是10次）

int M = 10;
	while (M--)
	{
	 ++count;
    } 
1
2
3
4
5

综上我们可以算出它关于++count被执行的次数为F(N)=N^2+2*N+10次。实际中我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。 （所以常数具体为多少都不重要，反正要被取代为1）
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

根据大O的渐进表示法,F(N)中常数是10,最高阶项是N^2 ,但最高阶项的系数是1，所以最终结果为N^2。

另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

大家可以看看下面这张图，可以方便快速判断出最高阶项。

要注意：不管时间复杂度的函数F(N)是一个怎样的函数表达式，我们都要第一时间找到对函数影响最大的项，如：F(N)=N*logN+20N+100000+N^2+logN，这个表达式的项虽然不少，但通过下图我们可以快速判断出 N^2 的影响是最大的，多以整体可以简化为N^2。

O(n!) >  O(2^n) >  O(n^3) > O(n^2) > O(n*logn) > O(n) > O(logn) > O(1) 
1

通过上面这些内容我们对时间复杂度有了初步的了解，下面我们再通过两个案例来做进一步了解。

void BubbleSort(int* a, int n)
{
	 assert(a);
 	for (int end = n; end > 0; --end)
 	{
		 int exchange = 0;
		 for (int i = 1; i < end; ++i)
 		{
			 if (a[i-1] > a[i])
		     {
 				Swap(&a[i-1], &a[i]);
 				exchange = 1;
 			 }
 	     }
 		 if (exchange == 0)
             break;
     }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

上面是一个冒泡排序的函数代码，里面只有两个for循环的嵌套，再无其它循环之类的代码，对它进行如下分析：
当外层for循环里的end为n时，内层for循环要执行end-1次，也就是n-1次，当外层for循环里的end为n-1时，内层for循环要执行end-1-1次，也就是n-2次，依次下去，当外层for循环里的end为2时，内层for循环要执行1次，当外层for循环里的end为1时，内层for循环结束，会发现如果两层for循环走完，那内层for循环要被执行的次数刚好是一个等差数列，由等差数列的公式可得F(N)=1/2N^2-1/2N, 再由大O的渐进表示法可以化简为N^2，这是时间复杂度最差的情况。
在冒泡排序中，如果某一趟排序走完，一个元素也没有被置换过位置，那说明所有元素已经有序了，两层for循环直接终止。

所以当数列原本就是顺序时不需要移动任何元素，时间复杂度最好，为O(1)，当数列原本就是逆序时，时间复杂度最差，为O(N^2)。
由于我们一般只考虑算法的最差时间复杂度，所以冒泡排序的时间复杂度为为O(N^2)。

 int Fib(int N)
 {
 	if(N < 2)
	 return n;
 
 	return Fib(N-1) + Fib(N-2);
 }
1
2
3
4
5
6
7

上面是求斐波那契数的递归函数，这种递归函数的特点是每递归调用一次，都要开辟一个新的函数栈帧，当这个函数调用结束，函数栈帧再被销毁释放掉。

下面是当N=4时，函数递归调用的栈帧图（一定要记住，当被调用的函数运行结束时，开辟的函数栈帧也要随之被销毁）
如果把这张图空的地方补全，从上面这张函数调用图中可以看出，第一层共有2^0 个函数被调用，第二层共有2^1 次方个函数被调用，依次下去，第四层有2^3 个函数被调用，随着N的增大，空缺的地方可以忽略不计，那这样函数被调用的次数就是一个等比数列，由求等比数列的公式可以求得函数被调用的总次数为(2^N)-1。 其中一个函数的时间复杂度可以看作是常数级O(1),所以总的来说它的时间复杂度为O(2^N)。

通过上面的几个列子，我们对时间复杂度有了初步的认识，随着后面的学习，慢慢的我们会对它有一个更深入的了解。

3.空间复杂度

3.1 时间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定（我们可以理解为一个函数除了形参变量，其它被创建的变量所占空间都属于显示申请的额外空间）。

3.2 空间复杂度的算法

空间复杂度的判断相对于时间复杂度来说要简单很多。
下面我们还是通过上面几个案列来判断它们的空间复杂度。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N ; ++ i)
	{
 		for (int j = 0; j < N ; ++ j)
		{
			 ++count;
 		}
	 }
 
	for (int k = 0; k < 2 * N ; ++ k)	
 	{
		 ++count;
	}
	int M = 10;
	while (M--)
	{
	 ++count;
    } 
    printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这个函数的形参变量N不算，函数体内还有变量count、i、j、k、M，常数个变量只需要常数个空间，和问题规模N无关，所以它的空间复杂度是常数级O(1)。

void BubbleSort(int* a, int n)
{
	 assert(a);
 	for (int end = n; end > 0; --end)
 	{
		 int exchange = 0;
		 for (int i = 1; i < end; ++i)
 		{
			 if (a[i-1] > a[i])
		     {
 				Swap(&a[i-1], &a[i]);
 				exchange = 1;
 			 }
 	     }
 		 if (exchange == 0)
             break;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个函数的形参变量a,n不算，函数体内还有变量end、exchange、i，常数个变量只需要常数个空间，和问题规模N无关，所以它的空间复杂度是常数级O(1)。

 int Fib(int N)
 {
 	if(N < 2)
	 return n;
 
 	return Fib(N-1) + Fib(N-2);
 }
1
2
3
4
5
6
7

下面是当N=4时，函数递归调用的栈帧图（一定要记住，当被调用的函数运行结束时，开辟的函数栈帧也要随之被销毁）

像上面这个递归函数的特点是先沿着红线方向走到底，当这条红线方向最后一次递归调用函数Fib(1)时，已经到了最下面一层，被递归调用的函数Fib(1)结束时，它开辟的函数栈帧也随之被销毁，然后沿着黄线方向继续递归调用下一个函数Fib(0),当这个Fib(0)被递归调用结束时，Fib(2)也随之被递归调用完，那他们两个的函数栈帧也被销毁，就这样一直往下继续递归调用函数。
所以从上面分析可以看出来，同时存在的函数栈帧个数最多时等于这个函数递归调用图的层数，也就是等于N的值。而这个递归函数除了形参变量再没有其它变量，所以我们可以把函数的一次递归调用的空间复杂度看作是常数级，所以综合来说这个递归函数的空间复杂度为它们的乘积，再根据大O渐近表示法，最终结果为O(N)。

通过上面的学习，相信我们对时间和空间复杂度的算法已经有了一定的了解，但还是存在很多的不足，那就让我们通过后续的学习来加深对它的理解。