【数据结构】算法的复杂度分析：让你拥有未卜先知的能力

一、 前言

一个程序能用很多不同的算法来实现，那么到底那种算法是效率最高的呢？ 对此我们有两种方法： 第一种是事后统计法，既在编写之后，通过计时，比较不同算法编写的程序的运行时间，以此确定算法效率的高低。但是该方法的缺陷很大，会受到测试环境、数据规模的影响。 第二种是事前分析法，即在编写之前，依据一些统计方法对算法进行粗略估算，大致的估算出该算法的时间复杂度和空间复杂度，通过对比复杂度来评判那种算法的效率更高。

可以说，学会了如何分析一个算法的复杂度，就拥有了未卜先知的能力，即在这个算法被写出来之前，就能大致评判出这个算法的好坏。

二、时间复杂度

1、定义

*：在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

额......具体来举个例子吧。

void Func1(int N)
{
int count = 0;
// n*n次
for (int i = 0; i < N ; ++ i)
{
 for (int j = 0; j < N ; ++ j)
 {
 ++count;
 }
}
// 2*n次
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
// 10次
int M = 10;
while (M--)
{
 ++count;
}
printf("%d\n", count);
}

这个函数一共执行的基本操作次数为：$F(n)=n^2+2*n+10$ 但是，我们计算复杂度的时候，不一定需要计算这么精确的执行次数，我们只需要计算出大概的执行次数就行了，所以这里我们应该使用大O的渐进表示法。那么什么是大O表示法呢？

2、大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为（趋向于特定值或无穷大）的数学符号。

上面函数一共执行的操作次数为：$F(n)=n^2+2n+10$ 学过极限的都知道，当$n$趋向于无穷的时候，$n^2+2n+10$ 中的$2*n$和10可以忽略不记。 所以用大O的渐进表示法，上面函数的时间复杂度应该为：$O(n^2)$ 这里我们可以简单的总结一下方法： 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中，只保留最高阶项。 3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。 4、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。

3、常见的时间复杂度

• $O(1)$型

一般情况下，要算法的执行时间不随问题规模 n 的增加而增大，那么就是$O(1)$的时间复杂度

void Func(int n)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

以上代码看似存在循环，但是仔细看，当循环到第十次的时候，这个循环就停止了。 所以上面的时间复杂度为 $O(1)$

• $O(logn)$型

类似于二分查找、幂运算都是$O(logn)$的时间复杂度

void Func(int n)
{
 int i=1;
 while (i <= n)  
 {
   i = i * 2;
 }
}

以上代码，变量 i 从 1 开始，每循环一次就乘以 2。当大于n时，循环结束。所以，假设一共循环了$x$次,那么我们就可以得到：$2^x=n$ 即$x=log_2n$ ，忽略掉底数2，则该时间复杂度为：$O(logn)$

为什么可以忽略掉底数？ 高中学过的换底公式：$log_bn=log_balog_an$ 现在假设底数不是2是3，我们可以把$log_3n$写成$log_32log_2n$，根据前面的规矩：如果最高阶项存在且不是1，则去除与这个项目相乘的常数。 而这里的$log_32$是个常数，可以直接去除。所以兜兜转转，最后的时间复杂度还是$O(logn)$

• $O(nlogn)$型

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

根据上面可以知道，这个循环里面的循环的复杂度是$O(logn)$，而这个循环又要执行n次，所以算下来，它的时间复杂度是$O(nlogn)$

• $O(n)$型

void Func(int n)
{
	for (int i = 1; i <= n; i++)
	{
		printf("我一共执行了n次哦！");
	}
}

• $O(n^2)$型

循环套循环，每个循环都是n次

void Func(int n)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			printf("我一共执行了n*n次哦！");
		}
	}
}

• $O(m*n)$型

void Func(int n,int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			printf("看的出来我有那些不一样吗？");
		}
	}
}

确实还有其他很多不同的时间复杂度，比如，$O(2^n)、O(n!)$...但是这些时间复杂度都太高了，以至于高到很多计算机都承受不了，所以比较少见。

三、空间复杂度

1、定义

*：在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示例如$O(n)、O(nlogn)$其中n用来表示输入的长度，该值可以影响算法的空间复杂度。

就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

2、常见的空间复杂度

• $O(1)型$

无论 n 的值如何变化，代码在执行过程中开辟的内存空间是固定的

void Func(int n)
{
	int i = 0; int sum = 0;
	for (i = 1; i < n; i++)
	{
		sum = sum + i;
	}
}

这段代码之开辟了sum和i两个int类型的空间，大小是固定的。 所以这段代码的空间复杂度为$O(1)$

• $O(n)型$

随着n的值的增大，开辟的空间也逐渐增大

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

这段代码递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。 所以这段代码的空间复杂度为$O(N)$

• $O(n^2)型$

  int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }

此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，所以是$n(n + 1)/2$个元素空间，空间复杂度为$n^2$