神秘海域[动图] 数据结构和算法初探复杂度 「」

---

---

复杂度 引言

复杂度，是贯穿整个数据结构与算法学习的一个重要概念。

它是衡量一个算法好坏的重要指标，它包括两个维度：时间、空间，被称为 时间复杂度、空间复杂度。
时间复杂度 主要衡量一个算法的运行快慢
空间复杂度 主要衡量一个算法运行所需要的额外空间

算法的复杂度，一般与需要处理的数据量挂钩，如果数据量为 N，那复杂度就有可能是：N 、 logN 、N*logN 、N^2 等等。

究竟什么是复杂度？

时间复杂度

上面提到：时间复杂度 主要衡量一个算法的运行快慢。
但是，这里的 快慢 并不是指 算法运行所需要执行的具体的时间。而是指：算法中的基本操作的执行次数。并且，算法的时间复杂度用一个函数表示.

举个简单的例子：

// 一个简单的循环
void Fun1(int n)
{
	for(int i = 0; i < n; i  )
	{
		printf("%d ", i);
	}
}

这段代码，for 循环执行的次数，是根据传入的参数来具体决定的，即循环 n 次。就可以说，这个函数的 时间复杂度是 O(N)。

看起来非常简单？

那么再看一个例子：

void Fun2(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;  
	}

}

函数 Fun2 中存在三个循环体，其中一个是嵌套的双重循环
那么，这个函数的 时间复杂度 是多少呢？该怎么计算？

逐个分析：

int count = 0;  
for (int i = 0; i < N ;    i)  
{  
	for (int j = 0; j < N ;    j)  
	{  
		  count;  
	}  
}  

这个循环是一个循环的嵌套，执行次数是 N*N

for (int k = 0; k < 2 * N ;    k)  
{  
	  count;  
}  

这个循环就是一个普通的循环，执行次数是 2*N

int M = 10;  
while (M--)  
{  
	  count;  
}

这个循环是 可以确定次数的循环，每次函数调用执行的次数是一定的，执行次数是 10 次

结合起来，这个函数的时间复杂度就是 O(N^2 2*N 10)
但是，事实并不是这样的。
这个函数的时间复杂度 其实是 O(N^2)
为什么？

来进行一个计算：

• N = 10， 执行次数：10*10 2*10 10 = 130
• N = 100， 执行次数：100*100 2*100 10 = 10210
• N = 1000， 执行次数：1000*1000 2*1000 10 = 1002010
• N = 10000， 执行次数：10000*10000 2*10000 10 = 100020010

有没有发现什么规律？
随着 N 的增大，2*N 10 在最终执行次数中的 占比越来越小 了，也代表着 其对最终执行次数的 影响越来越小 了
2*N 10 在结果中的占比： 23% -> 2% -> 0.2% -> 0.02%

当 N 足够大的时候，就已经可以忽略 2*N 10 的影响了，所以只需要计算 N^2 就能够代表函数的执行次数，所以 函数 Fun2 的时间复杂度 其实是 O(N^2)。

这时候计算时间复杂度，就只是计算了大概了执行次数，使用的是大 0 的渐进表示法

大 O 的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进 行为 的数学符号

用 大O表示法 计算复杂度的方法一般有：

1. 基本操作的执行次数中，相加的常数一般用 1 取代
   即：N^2 2*N 10 —> N^2 2*N 1
   或： O(100) —> O(1)，即常数的时间复杂度，均计算为 O(1)
2. 在常数转后之后的执行次数函数中，取最高次幂项作为时间复杂度，
   即： O(N^2 2*N 1) —> O(N^2)
3. 如果转换后的执行次数函数中，存在 最高次幂项 且 此项不为1，则只保留单个此项作为时间复杂度(即放弃与其相乘的常数)
   即：O(4 * N^2) —> O(N^2)

即，大O的渐进表示法 去掉了那些对结果影响不大的项 ，简洁明了的表示出了时间复杂度。
所以 函数Fun2 的时间复杂度为： O(N^2) 忽略了 2*N 10

时间复杂度的最好、最坏、平均情况

虽然知道了 大O渐进表示法 的计算方法，但是 总有一些算法代码是拥有多种情况的。
比如：

//查找整型数组中第一个 10 的位置
int Find_10(int *arr, int arrSize)
{
	int i = 0;
	while(arrSize--)
	{
		if(*arr == 10)
		{
			return i;	
		}
		arr  ;
		i  ;
	}

	return -1;
}

这个函数目的是寻找数组中第一个 10 的位置，但是 第一个 10 有可能出现在 一个数组中的任何位置，甚至不出现在数组中。

可能是 在 arr[0] arr[n - 1] arr[n / 2] ，被查找的数的位置是不定的，所以 这个函数中 基本操作的执行次数也是不定的。

那么这个时候，一个算法的时间复杂度，就用最坏情况下的复杂度来表示
Find_10 这个函数的时间复杂度，实际就是 O(N)。

「PS:计算基本操作的执行次数，结果中的未知数用 N 或 M 代表(只有一个未知数 用 N,两个未知数 用 N 和 M, 多个可以用其他)」

时间复杂度计算举例

// 计算Func1的时间复杂度？  
void Func1(int N)  
{  
	int count = 0;  
	for (int k = 0; k < 2 * N ;   k)  
	{  
		  count;  
	}
	
	int M = 10;  
	while (M--)  
	{  
		  count;  
	}  
	printf("%d\n", count);  
}

此函数，通过分析
拥有两个循环体，一个循环 2*N 次，另一个循环 10 次
按照 大O 渐进表示法，时间复杂度为 O(N)

// 计算Func2的时间复杂度？  
void Func2(int N, int M)  
{  
	int count = 0;  
	for (int k = 0; k < M;   k)  
	{  
		  count;  
	}  
	for (int k = 0; k < N ;    k)  
	{  
		  count;  
	}  
	printf("%d\n", count);  
}

此函数，通过分析
拥有两个循环体，一个循环 M 次，另一个循环 N 次
按照 大O 渐进表示法，时间复杂度为 O(M N)

// 计算Func3的时间复杂度？  
void Func3(int N)  
{  
	int count = 0;  
	for (int k = 0; k < 100;   k)  
	{  
		  count;  
	}  
	printf("%d\n", count);  
}

此函数，通过分析
有一个循环体，但是循环体循环次数与传入参数无关，固定循环 100 次
按照 大O 渐进表示法，时间复杂度为 O(1)

// 计算BubbleSort的时间复杂度？  
void BubbleSort(int* a, int n)  
{  
	assert(a);  
	
	for (size_t end = n; end > 0; --end)  
	{  
		int exchange = 0;  
		for (size_t i = 1; i < end;   i)  
		{  
			if (a[i-1] > a[i])  
			{  
				Swap(&a[i-1], &a[i]); 
				exchange = 1;  
			}  
		}  
		if (exchange == 0)  
			break;  
	}  
}

此函数为冒泡排序（排升序）
需要分情况分析：
最好的情况是：除了第一位其他都已位升序，则只需要循环 N 次，即 将第一位数据冒泡至最后一位
最坏的情况是：数据按照降序排列，则每一个数据都要进行排序，计算执行次数的结果为：(N*(N 1)/2 次
按照 大O 渐进表示法，取最坏的情况时间复杂度为 O(N^2)

// 计算BinarySearch的时间复杂度？  
int BinarySearch(int* a, int n, int x)  
{  
	assert(a);  
	
	int begin = 0;  
	int end = n-1;  
	while (begin < end)  
	{  
		int mid = begin   ((end-begin)>>1);  
		if (a[mid] < x)  
			begin = mid 1;  
		else if (a[mid] > x)  
			end = mid;  
		else  
			return mid;  
	}  
	
	return -1;  
}

此函数为二分查找，(被查找的数据必须是有序的)
同样需要分情况分析：
最好的情况：指定数据在数组中间位置，只需要执行一次，即第一次查找就查找到指定数据
最坏的情况：

二分查找的原理：因为使用二分查找的数据必须是有序的，所以可以通过缩小查找范围来进行查找
二分查找每次查找一次，下一次查找的范围会缩小为当前范围的一半
只需要一张动图就可解释：

可以看出，每次查找之后，下一次需要查找的元素只剩下一半，所以最坏的情况其实是 需要查找：log N次
复杂度中，log N即为 以2为底N的对数

所以按照 大O 渐进表示法，取最坏的情况时间复杂度为 O(log N)

// 计算阶乘递归Fac的时间复杂度？  
long long Fac(size_t N)  
{  
	if(0 == N)  
		return 1;  

	return Fac(N-1)*N;  
}

此函数为 递归求阶乘
递归求阶乘，通过计算可以算出，求N的阶乘 则函数调用了 N次
所以按照 大O 渐进表示法，时间复杂度为 O(N)

// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)  
{  
	if(N < 3)  
		return 1;  
		
	return Fib(N-1)   Fib(N-2);  
}

此函数为 递归求斐波那契数列
递归求斐波那契数列，一个简单的递归分析图：

发现正常调用函数，会再发生两次递归，所以应该是 2^N
但是因为当 N < 3 会返回 1，不再递归，所以应该是 2^N - x (不容易计算所以用 x 表示)，但是无论怎样，相减的常数因该是对2^N 造不成多大影响的
所以按照 大O 渐进表示法，时间复杂度为 O(2^N)

---

练习结束，感觉如何？？

空间复杂度

空间复杂度 主要衡量一个算法运行所需要的额外空间
这里提到一个词：额外空间

为什么是 额外空间 ？
因为，函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，在函数运行前就已经确定了一部分空间，这些空间的占用不能由算法本身决定
所以，空间复杂度主要通过 函数在运行时候申请的额外空间 来确定。

这里推荐一篇 详细又简单 的 函数栈帧 的好文章：
【程序员的自我修养】[动态图文] 超详解函数栈帧

在函数内使用动态开辟内存的函数，以及创建柔性数组等操作，就会增加函数的额外空间哦

空间复杂度 和 时间复杂度 的表示方法一样，都用 大O渐进表示法。

空间复杂度的计算举例

依然举几个例子：

// 计算BubbleSort的空间复杂度？  
void BubbleSort(int* a, int n)  
{  
	assert(a);  
	
	for (size_t end = n; end > 0; --end)  
	{  
		int exchange = 0;  
		for (size_t i = 1; i < end;   i)  
		{  
			if (a[i-1] > a[i])  
			{  
				Swap(&a[i-1], &a[i]); 
				exchange = 1;  
			}  
		}  
		if (exchange == 0)  
			break;  
	}  
}

分析代码可以看出，冒泡排序额外使用的空间并没有与 N 发生关联。使用了常量个额外空间
所以 按照 大O 渐进表示法，空间复杂度为 O(1)

// 计算Fibonacci的空间复杂度？  
// 返回斐波那契数列的前n项  
long long* Fibonacci(size_t n)  
{  
	if(n==0)  
		return NULL;  
	long long * fibArray = (long long *)malloc((n 1) * sizeof(long long));  
	fibArray[0] = 0;  
	fibArray[1] = 1;  
	for (int i = 2; i <= n ;   i)  
	{  
		fibArray[i] = fibArray[i - 1]   fibArray [i - 2];  
	}  
	
	return fibArray;  
}

这是使用 数组实现的计算斐波那契数列的 前N 项
分析代码可以看出，这段代码 使用 malloc 函数开辟了 n 1 个 long long类型的空间，即额外使用的空间与 N 1:1相关
所以 按照 大O 渐进表示法，空间复杂度为 O(N)

// 计算阶乘递归Fac的空间复杂度？  
long long Fac(size_t N)  
{  
	if(N == 0)  
		return 1;  
		
	return Fac(N-1)*N;  
}

递归求N的阶乘
分析代码可以看出，代码执行需要递归 N 次，且每次递归都需要开辟函数栈帧，每次函数栈帧开辟都会消耗常量个空间，所以是 常量 * N
按照 大O 渐进表示法，空间复杂度为 O(N)

---

以上内容就是 关于 时间复杂度 和 空间复杂度 的介绍。
复杂度需要进行学习的已经介绍的差不多了。
但是，需要注意的是
其实大部分的代码，时间、空间复杂度是不容易直接看出来的，一定要执行分析。对存在循环体的代码，也不要直接简单粗暴的去数循环体执行的次数，因为循环并不一定是都需要执行的。一定要分析。

---

复杂度对比

常见的复杂度都有什么呢？

---

结束语

---

感谢阅读！

求三连！求三连！

这篇好文章是转载于：学新通技术网