一、C语言后的基础数据结构的简单学习

（一、）时间复杂度和空间复杂度的计算

1.当我们写了一个代码是时候，会发现其实这个代码的写法会有非常多种，几乎每个人写的代码都是不一样的，所以这边我们就非常想知道这么多不同的代码中到底那个代码的算法更好，那个代码的效率更高，所以此时我们这边就会引入一个新的概念：时间复杂度和空间复杂度；所以接下来我们就讲一下什么是复杂度；

（1.）时间复杂度的概念和我如何进行对一个代码的时间复杂度的计算

（1.1）时间复杂度的概念：在计算机科学中时间复杂度其实就是一个函数（此时这个函数不是C语言中的函数，而是数学中的函数），它定量的描述了一个算法运行所需要的时间（但是此时如果使用算法的运行所需要的时间来断定一个代码算法的好坏，这样误差就非常大了（因为不同电脑，硬件的不同）），然后又因为一个算法运行的时间是和其中语句的执行次数是成正比例的（就比方说我执行一个语句的时间是多少多少秒，这样我就可以通过一个算法执行了几条语句来得到我此时这个算法运行所需要的时间了），所以此时我们就可以通过算法中的基本操作的执行次数，为一个算法的时间复杂度；

（1.2）所以总的来说时间复杂度就是我这个算法基本要执行的语句的次数（这边千万不敢再把时间复杂度就简单的理解成了一个与时间有关的概念了）（要理解为语句执行的次数）

（1.3）有了关于时间复杂度的概念，我们这边就来讲一个应该如何进行对时间复杂度的计算，让我们可以更好的理解一下时间复杂度（有关各种基础小算法的计算）

（1.3.1）首先这边我们来一个小题目（问一下这个代码的时间复杂度具体是多少？）（O(N^2)）

所以我们根据上述所说，我们此时对这个代码进行一定的理解就可以发现，此时这个代码的时间复杂度就是（F(N) = N * N + 2*N + 10）,因为时间复杂度是一个数学函数，所以这边我们写成这样，所以此时的F（N ）就是我们这个代码的具体的时间复杂度了，但是此时因为我的N是一个未知的值，所以此时就有一个规定（就是当我们的N是一个未知值的时候，此时我们就可以把那些常数值给省略，因为它对我这个代码的时间复杂度的影响是非常小的，并且因为N * N在N非常大的时候，此时2 * N 的影响也是非常小的，所以也可以省略，所以当我们在进行对一个代码是时间复杂度就行计算的时候，我们可以知道我么要算的只是一个大概的值，不一定要想上述那么的精确），所以此时按照这个说法，此时这个代码的时间复杂度就是F(N) = N * N,说以此时按照我们正规的时间复杂度的写法（也就是大O的渐进表示法），此时我们就把这个世间复杂度写成 O（N^2）;所以我们在算时间复杂度时，我们计算的就只是对代码运行次数结果影响最大的哪一项就行

这边我们单独的讲一下什么是大O的渐进表示法和推导大O阶的方法：

1.用常数 1 取代运行时间中的所有加法常数；

2.在修改后的运行次数函数中，只保留最高阶项；

3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数，此时得到的结果就是大O阶；

（1.3.2）我们这边再来一个题目进行对如何计算时间复杂度的讲解

有了上述知识我们这边就可以知道我们这个题目的时间复杂度就是O（N）

有了上述知识我们这边就可以知道我们这个题目的时间复杂度就是O（N + M）

有了上述知识我们这边就可以知道我们这个题目的时间复杂度就是O（1），按照推导O阶的方法可以知道，只要语句的执行的次数是一个常数项，我们这边就可以写成O（1），这个就是表示常数项的意思

（1.3.3）有了以上的例子，此时我们也就步对这个时间复杂度的计算多加讲解了，给出几个例题，咱们自己再理解一下就行了；

1.冒泡排序 时间复杂度：精确：（F（N）= N * (N-1)/2（等差数列的求和N-1到 1 的等差数列）估算：O（N^2）

2.二分查找法 这种算法此时就会有3种不同的情况（最快 平均 最坏），所以当一个算法有几种可能时，我们此时是以这个算法的最坏的那个情况进行判定这个算法的时间复杂度的，所以此时二分查找法的时间复杂度是：O（log以2为底N的对数）（主要的原因也就是二分查找的原理）

3.斐波那契数列 时间复杂度：O（2^N）具体原因也就是斐波那契数列的原理

（2.）空间复杂度

上述讲完了时间复杂度和其的计算，这边我们就讲一下什么是空间复杂度和空间复杂度的计算

（2.1）空间复杂度也是一个数学函数表达式，是对一个算法在运行过程中临时占用存储空间大小的量度，所以空间复杂度不是程序占用了所少个字节的空间，而是代表此时这个代码运行时临时的额外使用的变量的个数，并且与时间复杂度的表示方法类似，也是用大O渐进表示法

（2.2）空间复杂度的计算（把刚刚算的那些时间复杂度的题目再用来算一下空间复杂度）

得：1.

这个题目的空间复杂度其实就是：O（1）,为什么是O（1）呢？原因就是当我们在定义额外变量的时候，这个代码在循环时，这个代码向栈帧申请了空间，此时当我们循环完一次时，这个变量会同时销毁，但是进行下一次循环的时候，这个变量的空间其实还是原来的那块空间，所以此时这整个代码的循环就是一个变量的销毁，重新创建，销毁，创建的过程，所以此时本质上就只申请了一个额外的空间（只是可以利用这个空间进行循环使用而已），所以此时只使用了常数个额外的变量，所以此时的空间复杂度就是O（1）

2.下面是有关阶乘的空间复杂度的计算：

附上一幅图，便于理解：

所以此时根据我们上述的知识和具体的原理，可以很容易得知，这个阶乘的空间复杂度是：O（N）

因为我开辟了N个额外的空间，此时的空间并不是同一块位置，是 N个不同的变量的空间

3.下面是有关斐波那契数列的空间复杂度的计算：

附上一幅图，便与理解：

所以此时根据原理，可知斐波那契数列的空间复杂度是：O（N）

肯定有人会问为什么呢？

这边我们就要注意一点（空间是可以重复利用的，不累计的，而时间是一去不复返的，累计的）

原因就是我的栈的大小是有限的，这个栈是可以重复使用的此时栈的空间的大小，所以此时的这个栈就是在重复的使用N次，因为我的递归最大一次就是N次

（3.）总结：所以以上就是时间复杂度和空间复杂度的一些讲解

（二、）线性表中的顺序表的讲解

1.个人原因，非常不好意思，主要是明天神奇学校又要晨跑（5点多就要起床），所以这块我们明天写