【初阶数据结构与算法】新的旅程之时间复杂度和空间复杂度

一、前言

1.什么是数据结构

   数据结构(DataStructure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合
   没有⼀种单⼀的数据结构对所有⽤途都有⽤，都有各自的优缺点和应用领域，所以我们要学各式各样的数据结构，如：线性表、树、图、哈希等，然后就可以在不同场景下很好的使用和管理数据
   在之前我们已经学习完了C语言，接下来我们【初阶数据结构与算法】的内容主要就是使用C语言来实现一些常用的初阶数据结构，通过相关OJ题来学习一些算法，最后我们会将所有排序算法一一讲解，然后就进入C++的部分，至于高阶数据结构和算法我们会在C++部分穿插讲解

2.什么是算法

   算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出，简单来说，算法就是在程序中使用某种方法，使得我们输入的值能够得出正确的结果，这个方法就是一种算法
   比如输入一个数字n，求第n个斐波那契数，使用递归可以实现这个效果，使用迭代也可以实现，总之通过这两种方法可以通过输入的n，输出最后正确的结果，那么它们就是两种不同的算法
   那么很容易想到，解决同一个问题会有不同的方法，也就是会有不同的算法，那么一般情况下不同的算法会有优有劣，在上面的例子中，求第n个斐波那契数很明显使用迭代会好得多，那么我们怎么判断我们写出来的程序是好是坏呢？
   这就是我们今天要学习的内容，我们可以通过分析程序使用的算法的时间复杂度和空间复杂度来衡量它的优劣，让我们慢慢往后学习

3.数据结构和算法的重要性

   众所周知，数据结构和算法是各种竞赛考察的重点和难点，同时在校招里面它们也是企业考察学生学习的一个手段，基本上是必考内容
   那么想要学好数据结构和算法的秘诀就是，死磕代码，一遍不会再来一遍，同时也要画图画图画图+思考，理解代码里的每一步
   在开始正式学习前，我们先来推荐几本数据结构相关的书籍：

1. 《数据结构》严蔚敏，推荐理由：C语⾔版本，内容详尽，代码规整，各⼤院校指定教材
   

2. 《数据结构》殷⼈昆，推荐理由：C++版本，内容详尽，代码规整
   

3. 《⼤话数据结构》程杰，推荐理由：趣味易读，算法讲解细致深刻
   

4. 《算法导论》Thomas H. Cormen(托⻢斯•科尔曼),推荐理由：叙述严谨，内容全⾯，深⼊讨论各类算法，适合进阶学习
   

二、时间复杂度

1.复杂度的概念

   算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源，因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度，时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间
   在计算机发展的早期，计算机的存储容量很⼩，所以对空间复杂度很是在乎，但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度，所以我们如今已经不需要再特别关注⼀个算法的空间复杂度，但是在做算法题时一般还是会限制程序运行的空间大小

2.时间复杂度函数式

   定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间，时间复杂度是衡量程序的时间效率，那么为什么不去计算一个程序的运行时间，然后用程序的运行时间来衡量程序的时间复杂度呢？我们总结了以下4点原因：

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同
2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同
3. 程序的运行时间只能程序写好后测试，不能写程序前通过理论思想计算评估
4. 同一个程序在同一台机器上的每次的运行时间不一定相同

   所以算法的时间复杂度是用⼀个函数式T(N)来衡量的，那么它到底是什么呢？这个T(N)函数式用来计算程序中所有语句的执⾏次数，其中的N就是我们输入的数据，我们在计算时间复杂度时关注的就是用户输入的数据对程序时间的影响
   在这个函数式中，我们假设每句指令执⾏时间基本⼀样(实际中有差别，但是微乎其微)，那么语句的执⾏次数和运⾏时间就是等⽐正相关，这样也脱离了具体的编译运⾏环境，执⾏次数就可以代表程序时间效率的优劣
   ⽐如解决⼀个问题的算法a程序的时间复杂度T(N)=N，算法b程序的时间复杂度T(N)=N^2，用户输入的就是N，a程序相当于就会多执行N条语句，而b程序相当于会多执行N ^2条语句，很明显算法a的效率⼀定优于算法b
   接下来我们来看一个案例，试着分析它的时间复杂度函数式T(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;
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
}

   这个应该不是很难，就和平常的函数差不多，经过分析， Func1执⾏的基本操作次数大致为：

T(N) = N^2 + 2 ∗ N + 10

   为了方便解释，这里我们稍微取了一个整，那么接下来我们来列举一下，当N在变化时，每一项对语句执行次数影响的大小：

• 当N=10时，T(N)=130
• 当N=100时，T(N)=10210
• 当N =1000时，T(N)=1002010

   通过对N的取值分析，我们可以看出来，N^2对结果的影响最大，实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)
   并且计算出精确的执⾏次数意义也不⼤，因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，所以复杂度的表⽰通常使⽤⼤O渐进表⽰法

3.大O渐进表示法

   大O符号（BigOnotation）：是⽤于描述函数渐进⾏为的数学符号，使用大O渐进表示法后，我们不必将时间复杂度中程序运行的次数计算得十分精确，只需要推出一个大概次数，那么接下来我们来看看大O渐进表示法的几条规则：

1. 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了，比如：

//时间复杂度函数式
T(N) = N^2 + 2 ∗ N + 10
//使用大O渐进表示法后：
O(N) = N^2（只保留最高阶）

2. 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了，比如：

//时间复杂度函数式
T(N) = 2 ∗ N + 10
//使用大O渐进表示法后：
O(N) = N //去掉系数和常数

3. T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数，比如：

//时间复杂度函数式
T(N) = 10
//使用大O渐进表示法后：
O(1)//函数式中只有常数，直接用O(1)表示

4. 如果T(N)中的N不确定最后会取到多少，那么就以最坏的情况为最后结果，比如：

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	while (*p_begin != character)
	{
		if (*p_begin == '\0')
			return NULL;
		p_begin++;
	}
	return p_begin;
}

   这里代码执行多少次就不确定了，如果要查找的字符在第一个，那么就只执行一次，在中间的话就执行N/2次，如果在最后面就执行N次，所以这个时候我们一般会取最坏的结果作为它的时间复杂度，即O(N) = N
   现在我们就了解了大O渐进表示法了，接下来我们继续看几道例题

4.练习

练习1

   计算以下案例中的时间复杂度，统一先写出函数式T(N)，随后将其使用大O渐进表示法表示：

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

   第一道例题非常简单，首先我们可以分析出它的函数式T(N) = 2 * N + 10，要注意的是，里面的M不会随着用户的输入而改变，它的值只是10，后面的for循环只会循环10次，所以是常数
   首先，根据大O渐进表示法的第一条规则，只保留最高次，这里的最高次就是N的一次方，所以根据第一条规则只保留2*N，根据第二条规则，要将最高次的系数改成1，所以我们最后可以得出这道例题的答案：O(N) = N

练习2

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

   这里可以看出来，传过来的N根本没有用上，代码只执行了100次，所以根据大O渐进表示法第3条规则，这段代码的时间复杂度为：O(1)

练习3

void func5(int n)
{
    int cnt = 1;
    while (cnt < n)
    {
        cnt *= 2;
    }
}

   这个和之前的例子都有点不一样，我们可以试着来列举一下：当n=2时，执⾏次数为1，当n=4时，执⾏次数为2，当n=16时，执⾏次数为4
   那么假设执⾏次数为x，则2^x = n，所以执⾏次数：x = log n，其中的底为2，因此：func5的时间复杂度取最差情况为：O(log n)
   观察仔细的同学可能就发现了，这里我们最后写出的时间复杂度的大O表示法中的对数没有底数，这是为什么呢？这就要涉及到它的又一个规则了：
   当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为logn，不同书籍的表⽰⽅式不同，以上写法差别不⼤，所以我们建议使⽤logn

三、空间复杂度

   学习了时间复杂度再来学习空间复杂度就要简单得多了，空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间
   空间复杂度不是程序占⽤了多少字节的空间，因为常规情况每个对象⼤⼩差异不会很⼤，比如字符型1个字节，整型4个字节，浮点型4个字节，差别都不是很大，所以空间复杂度算的是我们创建的变量的个数
   空间复杂度计算规则基本跟时间复杂度类似，也使⽤⼤O渐进表⽰法，规则和时间复杂度那里一致，所以学习了时间复杂度再来学习空间复杂度的表示方法就简单得多
   注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定
   现在我们来看几个例子

练习

练习1

   还是老样子，我们使用大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;
}

   这个案例是我们曾经学过的冒泡排序，可以看到它并没有去循环地申请变量，也就说明它创建的变量是常数个数的，所以冒泡排序的空间复杂度就可以表示为：O(1)，那么冒泡排序的时间复杂度是多少呢？可以自行根据之前的例子分析一下，可以把答案写到评论区，我来帮你们来看看是否正确~

练习2

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

   这里的Fac函数使用递归来求阶乘，很明显每递归一次就要创建一个函数栈帧，那么一共要递归N次，所以最后它的空间复杂度就是O(N)

四、常见复杂度对比

   今天是10月的最后一天，我们的学习之旅不会结束，今天也是我们新的开始：数据结构与算法，如果有什么地方没有写对的欢迎各位大佬指正
   今天就到这里啦，bye~